#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define maxn 1000000
using namespace std;
int n;
long long ans=0;
char s[2*maxn];
int d[2*maxn];
int seg[8*maxn];
void update(int id,int l,int r,int p,int v) {
if(l==r) {
seg[id]=v;
return;
}
int m=(l+r)>>1;
if(p<=m) update(id*2+1,l,m,p,v);
else update(id*2+2,m+1,r,p,v);
seg[id]=seg[id*2+1]+seg[id*2+2];
}
int query(int id,int l,int r,int x,int y) {
if(x<=l && r<=y) return seg[id];
if(r<x || y<l) return 0;
int m=(l+r)>>1;
return query(id*2+1,l,m,x,y)+query(id*2+2,m+1,r,x,y);
}
int l[maxn];
int r[maxn];
long long val(int i) {
int cb=0;
int x=0;
int y=0;
long long cans=0;
int tmp=0;
while(cb<i || s[y]!='B') {
if(s[y]=='B') cb++;
y++;
if(y==2*n) y=0;
}
int k=1;
l[k]=x;
r[k]=y;
d[x]=-k;
d[y]=k;
x++;
while(x<2*n) {
if(s[x]=='W') {
k++;
do {
y++;
if(y==2*n) y=0;
} while(s[y]!='B');
l[k]=min(x,y);
r[k]=max(x,y);
d[min(x,y)]=-k;
d[max(x,y)]=k;
}
x++;
}
for(int i=0;i<2*n;i++) {
if(d[i]>0) {
update(0,0,2*n-1,l[d[i]],0);
cans+=query(0,0,2*n-1,l[d[i]],r[d[i]]);
}
else update(0,0,2*n-1,i,1);
}
return cans;
}
int main() {
scanf("%d",&n);
scanf("%s",s);
if(s[0]=='B') {
for(int i=0;i<2*n;i++) {
if(s[i]=='B') s[i]='W';
else s[i]='B';
}
}
int l=0,r=n-1;
while(l<r) {
int m1=(l+r)>>1;
int m2=m1+1;
long long v1=val(m1);
long long v2=val(m2);
ans=max(ans,v1);
ans=max(ans,v2);
if(v1>v2) r=m2-1;
else l=m1+1;
}
ans=max(ans,val(l));
printf("%lld",ans);
return 0;
}
Compilation message
monochrome.cpp: In function 'long long int val(int)':
monochrome.cpp:33:9: warning: unused variable 'tmp' [-Wunused-variable]
33 | int tmp=0;
| ^~~
monochrome.cpp: In function 'int main()':
monochrome.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
69 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
monochrome.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
70 | scanf("%s",s);
| ~~~~~^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
3 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
512 KB |
Output is correct |
23 |
Correct |
2 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
512 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
2 ms |
384 KB |
Output is correct |
28 |
Correct |
2 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
3 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
512 KB |
Output is correct |
23 |
Correct |
2 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
512 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
2 ms |
384 KB |
Output is correct |
28 |
Correct |
2 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
16 ms |
512 KB |
Output is correct |
35 |
Correct |
17 ms |
384 KB |
Output is correct |
36 |
Correct |
22 ms |
384 KB |
Output is correct |
37 |
Correct |
16 ms |
384 KB |
Output is correct |
38 |
Correct |
14 ms |
416 KB |
Output is correct |
39 |
Correct |
14 ms |
384 KB |
Output is correct |
40 |
Correct |
13 ms |
504 KB |
Output is correct |
41 |
Correct |
15 ms |
384 KB |
Output is correct |
42 |
Correct |
16 ms |
384 KB |
Output is correct |
43 |
Correct |
15 ms |
384 KB |
Output is correct |
44 |
Correct |
14 ms |
384 KB |
Output is correct |
45 |
Correct |
14 ms |
384 KB |
Output is correct |
46 |
Correct |
17 ms |
384 KB |
Output is correct |
47 |
Correct |
17 ms |
384 KB |
Output is correct |
48 |
Correct |
15 ms |
384 KB |
Output is correct |
49 |
Correct |
13 ms |
384 KB |
Output is correct |
50 |
Correct |
16 ms |
384 KB |
Output is correct |
51 |
Correct |
15 ms |
384 KB |
Output is correct |
52 |
Correct |
15 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
3 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
512 KB |
Output is correct |
23 |
Correct |
2 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
512 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
2 ms |
384 KB |
Output is correct |
28 |
Correct |
2 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
16 ms |
512 KB |
Output is correct |
35 |
Correct |
17 ms |
384 KB |
Output is correct |
36 |
Correct |
22 ms |
384 KB |
Output is correct |
37 |
Correct |
16 ms |
384 KB |
Output is correct |
38 |
Correct |
14 ms |
416 KB |
Output is correct |
39 |
Correct |
14 ms |
384 KB |
Output is correct |
40 |
Correct |
13 ms |
504 KB |
Output is correct |
41 |
Correct |
15 ms |
384 KB |
Output is correct |
42 |
Correct |
16 ms |
384 KB |
Output is correct |
43 |
Correct |
15 ms |
384 KB |
Output is correct |
44 |
Correct |
14 ms |
384 KB |
Output is correct |
45 |
Correct |
14 ms |
384 KB |
Output is correct |
46 |
Correct |
17 ms |
384 KB |
Output is correct |
47 |
Correct |
17 ms |
384 KB |
Output is correct |
48 |
Correct |
15 ms |
384 KB |
Output is correct |
49 |
Correct |
13 ms |
384 KB |
Output is correct |
50 |
Correct |
16 ms |
384 KB |
Output is correct |
51 |
Correct |
15 ms |
384 KB |
Output is correct |
52 |
Correct |
15 ms |
384 KB |
Output is correct |
53 |
Execution timed out |
2025 ms |
7032 KB |
Time limit exceeded |
54 |
Halted |
0 ms |
0 KB |
- |