#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int dizi1[500005];
int dizi2[500005];
int seg1[2000005];
int seg2[2000005];
int segment(int x,int l,int r,int bas,int son)
{
if(r<bas||l>son)
return 0;
if(l>=bas&&r<=son)
return max(seg1[x],0);
int orta=(l+r)/2;
return max(segment(x*2,l,orta,bas,son),max(segment(x*2+1,orta+1,r,bas,son),0));
}
int segment2(int x,int l,int r,int bas,int son)
{
if(r<bas||l>son)
return 0;
if(l>=bas&&r<=son)
return max(seg2[x],0);
int orta=(l+r)/2;
return max(segment2(x*2,l,orta,bas,son),max(segment2(x*2+1,orta+1,r,bas,son),0));
}
int build2(int x,int bas,int son)
{
if(bas==son)
return seg2[x]=dizi2[bas];
int orta=(bas+son)/2;
seg2[2*x]=build2(2*x,bas,orta);
seg2[2*x+1]=build2(2*x+1,orta+1,son);
return seg2[x]=max(seg2[2*x],seg2[2*x+1]);
}
int build(int x,int bas,int son)
{
if(bas==son)
return seg1[x]=dizi1[bas];
int orta=(bas+son)/2;
seg1[2*x]=build(2*x,bas,orta);
seg1[2*x+1]=build(2*x+1,orta+1,son);
return seg1[x]=max(seg1[2*x],seg1[2*x+1]);
}
int main()
{
scanf("%d",&n);
cin>>s;
s="U"+s;
if(s[1]=='C')
dizi1[1]=-1;
else dizi1[1]=1;
for(int i=2;i<=n;i++)
{
if(s[i]=='C')
dizi1[i]=dizi1[i-1]-1;
else dizi1[i]=dizi1[i-1]+1;
}
if(s[n]=='C')
dizi2[n]=-1;
else dizi2[n]=1;
for(int i=n-1;i>=0;i--)
{
if(s[i]=='C')
dizi2[i]=dizi2[i+1]-1;
else dizi2[i]=dizi2[i+1]+1;
}
build(1,1,n);
build2(1,1,n);
int q;
scanf("%d",&q);
while(q--)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",max(segment(1,1,n,a,b)-dizi1[a-1],segment2(1,1,n,a,b)-dizi2[b+1]));
}
return 0;
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
election.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
election.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
