QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#785071#7717. BitsetsyhdddAC ✓1045ms282864kbC++141.9kb2024-11-26 16:46:482024-11-26 16:46:49

Judging History

你现在查看的是最新测评结果

  • [2024-11-26 16:46:49]
  • 评测
  • 测评结果:AC
  • 用时:1045ms
  • 内存:282864kb
  • [2024-11-26 16:46:48]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read(){
	int x=0,fl=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*fl;
}
const int maxn=100010;
bool mbe;

int n,m;
int k,l,r,x,y,z,ans,res;
char s[maxn];
vector<int> a[maxn];
#define mid (l+r>>1)
#define ls lc[nd]
#define rs rc[nd]
int tree[maxn<<8],lc[maxn<<8],rc[maxn<<8];
int rt[maxn],idx;
void updata(int &nd,int l,int r,int p){
	int lst=nd;nd=++idx;
	tree[nd]=tree[lst]+1,ls=lc[lst],rs=rc[lst];
	if(l==r)return ;
	if(p<=mid)updata(ls,l,mid,p);
	else updata(rs,mid+1,r,p);
}
int query(int nd,int l,int r,int ql,int qr){
	if(ql>qr||!nd||!tree[nd])return 0;
	if(l>=ql&&r<=qr)return tree[nd];
	if(qr<=mid)return query(ls,l,mid,ql,qr);
	if(ql>mid)return query(rs,mid+1,r,ql,qr);
	return query(ls,l,mid,ql,qr)+query(rs,mid+1,r,ql,qr);
}
vector<int> upd[maxn];
void sovle(){
	n=read();m=read();
	for(int i=0;i<=n;i++)a[i].resize(m+1);
	for(int i=1;i<=n;i++){
		scanf("%s",s+1);
		for(int j=1;j<=m;j++)a[i][j]=(s[j]=='1');
	}
	for(int i=1;i<=m;i++){
		int lst=0;
		for(int j=2;j<=n;j++){
			if(a[j][i]!=a[j-1][i]){
				upd[lst+1].pb(j-1);
				lst=j-1;
			}
		}
		upd[lst+1].pb(n);
	}
	for(int i=1;i<=n;i++){
		rt[i]=rt[i-1];
		for(int j:upd[i])if(j>=i)updata(rt[i],1,n,j);
	}
	k=read();
	x=read(),y=read(),z=read(),l=1,r=n;
	for(int i=1;i<=k;i++){
		int ll=min(l,r),rr=max(l,r);
		ans=query(rt[ll],1,n,rr,n);
		res+=ans;
		l=(l*x+ans*y+z)%n+1;
		r=(r*y+ans*z+x)%n+1;
	}
	printf("%lld\n",res);
}

bool med;
int T;
signed main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	
	// cerr<<(&mbe-&med)/1024.0/1024.0<<" MB\n";
	
	T=1;
	while(T--)sovle();
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 11356kb

input:

4 10
1010110101
0101111001
1101101101
1011010000
4
10 5 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 0ms
memory: 11388kb

input:

6 3
110
011
010
100
101
111
5
7 5 5

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 0ms
memory: 11280kb

input:

10 10
1100101001
0011100101
1100001110
0101011100
1001011010
0010101101
1001011011
0010110000
1001100111
0010101000
10
11 11 11

output:

26

result:

ok 1 number(s): "26"

Test #4:

score: 0
Accepted
time: 1ms
memory: 9268kb

input:

6 7
1101001
1000110
0010000
1110001
1110100
0001011
15
7 5 7

output:

30

result:

ok 1 number(s): "30"

Test #5:

score: 0
Accepted
time: 0ms
memory: 11276kb

input:

10 13
0101011101010
0100000011001
0001101010111
1101000111100
1001110000110
0110011000110
1101101110100
0101101110011
0000100011100
1100010110100
20
11 11 11

output:

60

result:

ok 1 number(s): "60"

Test #6:

score: 0
Accepted
time: 2ms
memory: 11348kb

input:

12 15
010010101101011
010000100100011
110011010100011
111011101010111
101110111010100
100000111011011
010100001101100
001011010111100
000011011100010
101100101001010
010000111101111
110100011011000
25
11 13 13

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 1ms
memory: 9376kb

input:

15 16
1111010001110110
1111100101111111
1111111111001010
0010100111111001
1011011000001000
1111000101000000
1001101100100011
0010111000001110
0011111000010001
1000011111011111
1101000111000001
0010010100001011
1110001111111010
0011100110100001
0101110010101101
30
13 13 17

output:

448

result:

ok 1 number(s): "448"

Test #8:

score: 0
Accepted
time: 1ms
memory: 9384kb

input:

13 15
001100110010010
011100110100111
111100000000110
111000011101010
111100011001010
100111101001001
000110010111101
100101000000100
011010001000000
101001100011100
011110111111000
010110111100111
110010010100110
35
13 13 11

output:

0

result:

ok 1 number(s): "0"

Test #9:

score: 0
Accepted
time: 0ms
memory: 11400kb

input:

11 9
110101001
001010011
000100101
110011000
110101110
001001100
110100110
100110000
100010111
110110000
111100000
40
13 11 13

output:

47

result:

ok 1 number(s): "47"

Test #10:

score: 0
Accepted
time: 2ms
memory: 11340kb

input:

10 18
010111010010010001
111010101000100111
011010111100011001
000010000111001111
101010010000110100
001110000101111101
010101011011000100
111011110001010010
111010101101000000
100101010111101100
45
11 11 11

output:

353

result:

ok 1 number(s): "353"

Test #11:

score: 0
Accepted
time: 2ms
memory: 11348kb

input:

11 17
01100000011010100
11100001111000101
10011100111011011
10011110010011000
10110110111110010
01001001101111000
11010101101101110
01101101110001110
11101000000101001
00000110000001000
10001111001100010
50
13 11 13

output:

228

result:

ok 1 number(s): "228"

Test #12:

score: 0
Accepted
time: 1ms
memory: 9344kb

input:

1 1
0
1
2 2 2

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 1ms
memory: 11408kb

input:

1 10
0010001000
1
2 2 2

output:

10

result:

ok 1 number(s): "10"

Test #14:

score: 0
Accepted
time: 1ms
memory: 9276kb

input:

10 1
0
0
0
0
1
0
0
0
1
0
1
11 11 11

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 0ms
memory: 13688kb

input:

100 100
0001000000000000100100100100000000100100100010000000000000000000000010000000000010001000000000000000
0000000000000000000000000000000000000000000000000000000000100000010000000010001000000100001000000000
000000000000000000000000000001000000010001000000000000000000000000000000100000000000001000...

output:

709

result:

ok 1 number(s): "709"

Test #16:

score: 0
Accepted
time: 4ms
memory: 25668kb

input:

500 500
1011111111111111111111111111011111110111111101111111111111111111111101111111111111111111111111111111011111111111111101111110101111111111111111101111111111111101110101111111110111111101111111111110111100111111101111111101011111111111111111111111111111111111111011111101111111111111111111111111...

output:

1394

result:

ok 1 number(s): "1394"

Test #17:

score: 0
Accepted
time: 12ms
memory: 57544kb

input:

1000 1000
00000000000000000000000000010000001110000000001000000100000000000000000000000000000000000001000000001000000000000000000000000000000000100010000000000000000000000000000000100000100100100100000000000000000000000000001100000000000001100000000000000000000000000000010000100000000000010000000000...

output:

21974

result:

ok 1 number(s): "21974"

Test #18:

score: 0
Accepted
time: 11ms
memory: 54264kb

input:

10000 100
1110111111110111111111111111111111011111111111011111111011111111111011111111111111111101111111111111
1110111101111111111111111111111111111111110111111111111111111111011111111101111111111111111111111111
1111110111111111111111111111011111111111111111111111111111111111111111111101111111111111...

output:

3586

result:

ok 1 number(s): "3586"

Test #19:

score: 0
Accepted
time: 24ms
memory: 113480kb

input:

100 10000
00110000010011110000100010110001110000001000010010110100001100010000011100100001111000000010000001000100101001000000010101001100000010100011011001000101001110000100100100100110000111010100000000101000001100011001101101011000010001110110000010010000000000000011101101100010110010100111000011...

output:

1046213

result:

ok 1 number(s): "1046213"

Test #20:

score: 0
Accepted
time: 22ms
memory: 46448kb

input:

5000 200
11000000100100000000000010001000000000000000000000000000010000000000000000000001000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000100000000000000000000000000010000000000000000000000010000000100000000000100000001000...

output:

170424

result:

ok 1 number(s): "170424"

Test #21:

score: 0
Accepted
time: 27ms
memory: 40024kb

input:

5000 200
00000000000000000000000000000000000000000000000000000000000000000000000000000000100000001000000000000000000000010010000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000100000000000000001000010000000000000000000100000001000000000001000000000100000000000010...

output:

2499626

result:

ok 1 number(s): "2499626"

Test #22:

score: 0
Accepted
time: 271ms
memory: 34588kb

input:

5000 200
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000010000100000000000
000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000...

output:

35029587

result:

ok 1 number(s): "35029587"

Test #23:

score: 0
Accepted
time: 183ms
memory: 27540kb

input:

5000 200
00000000000000000000000000000000000000000010000000000000000000000000000000000000000000100000000010000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000
000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

16776

result:

ok 1 number(s): "16776"

Test #24:

score: 0
Accepted
time: 337ms
memory: 30360kb

input:

10 100000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2000000000000

result:

ok 1 number(s): "2000000000000"

Test #25:

score: 0
Accepted
time: 630ms
memory: 20712kb

input:

100000 10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111...

output:

200000000

result:

ok 1 number(s): "200000000"

Test #26:

score: 0
Accepted
time: 372ms
memory: 19344kb

input:

5000 200
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

4000000000

result:

ok 1 number(s): "4000000000"

Test #27:

score: 0
Accepted
time: 338ms
memory: 19976kb

input:

200 5000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

100000000000

result:

ok 1 number(s): "100000000000"

Test #28:

score: 0
Accepted
time: 1045ms
memory: 19296kb

input:

5000 200
01011011001100110010110011101100111001100010110000011111011010111011010100111001011000110010011100101111110001010101101100100001111001011111110100011101011011111101010111111101000000000000110010010100
010110110011001100101100111011001110011000101100000111110110101110110101001110010110001100...

output:

2834691058

result:

ok 1 number(s): "2834691058"

Test #29:

score: 0
Accepted
time: 427ms
memory: 29528kb

input:

50 20000
111100111010100100001111000001011000000100101110101011000101000000001101100110000110110011001000101000000000000010111101001000100010100000000000010101100011110100000010011110110111100110111100101010100011111100000110100100011100100001001011110010010101010001010011001100000100001100011111010...

output:

177674291006

result:

ok 1 number(s): "177674291006"

Test #30:

score: 0
Accepted
time: 809ms
memory: 234508kb

input:

100000 10
1011010110
1000000000
0100111001
1010000100
1000111011
1011110101
1010011001
0110001010
1110010110
0000000001
0101110011
1100000111
0100101100
0111101111
1100101001
1001100110
1011110111
0111000010
1011101111
0011100010
0100100011
1111010111
0010000011
0001000100
0100101010
1001100001
1010...

output:

14

result:

ok 1 number(s): "14"

Test #31:

score: 0
Accepted
time: 973ms
memory: 19608kb

input:

999 999
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

19939999183

result:

ok 1 number(s): "19939999183"

Test #32:

score: 0
Accepted
time: 904ms
memory: 282864kb

input:

999 999
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0

result:

ok 1 number(s): "0"