#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
char s[555555];
int n;
int del[555555];
int solve_naive(int l, int r)
{
int cnt=0;
for(int i=l;i<=r;i++) del[i]=0;
int ans=0; int S=0; int minpref=0;
for(int i=l;i<=r;i++)
{
S+=(s[i]=='C'?1:-1);
if(s[i]=='C') cnt++;
else cnt--;
if(cnt<0)
{
del[i]=1; ans++;
cnt++;
}
}
minpref=-ans;
int positive = S - minpref;
cnt=0; int mx=0;
for(int i=r;i>=l;i--)
{
if(del[i])
{
cnt = positive; continue;
}
if(s[i]=='C') cnt++;
else cnt--;
if(cnt<0)
{
mx=max(mx,abs(cnt));
}
}
return ans+mx;
}
int vec[20][511111];
int sufmax[20][511111];
int prefmax[20][511111];
struct node
{
int sum;
//vi vec;
//vi sufmax;
int minprefback;
//vi prefmax;
int lvl;
int l;
int len;
int lastneg;
};
node st[511111*4];
/*
void outnode(node S)
{
cout<<"SUM : "<<S.sum<<'\n';
for(int v:S.vec)
{
cout<<v<<' ';
}
cout<<'\n';
cout<<"MIN PREF FROM BACK : "<<S.minprefback<<'\n';
cout<<"LAST NEGATIVE : "<<S.lastneg<<'\n';
}
*/
node compute(int lvl, int l, int r)
{
node N;
N.l=l;
N.lvl=lvl;
N.sum=0;
N.len=0;
for(int i=l;i<=r;i++) del[i]=0;
int cnt=0; int minpref=0;
for(int i=l;i<=r;i++)
{
N.sum+=(s[i]=='C'?1:-1);
cnt+=(s[i]=='C'?1:-1);
if(cnt<0)
{
del[i]=1; cnt++; minpref--;
}
}
N.minprefback=0; cnt=0;
for(int i=r;i>=l;i--)
{
cnt+=(s[i]=='C'?1:-1);
N.minprefback=min(N.minprefback, cnt);
}
N.minprefback*=-1;
cnt=0; int mn = 0; bool ex=0; N.lastneg=0;
for(int i=r;i>=l;i--)
{
if(del[i])
{
if(!ex)
{
N.lastneg=abs(mn);
}
else
{
vec[lvl][l + (N.len++)]=abs(mn);
}
cnt=0; mn=0;
ex=1;
}
else
{
cnt+=(s[i]=='C'?1:-1);
mn = min(mn, cnt);
}
}
if(!ex)
{
N.lastneg = abs(mn);
}
else
{
vec[lvl][l + (N.len++)]=abs(mn);
}
int lef=l; int ri=l+N.len-1;
//cerr<<lef<<' '<<ri<<' '<<l<<' '<<r<<'\n';
assert(ri<=r);
int tmpl=lef; int tmpr=ri;
while(lef<ri)
{
swap(vec[lvl][lef],vec[lvl][ri]); lef++; ri--;
}
lef=tmpl; ri=tmpr;
//N.sufmax.resize(int(N.vec.size()));
for(int i=ri;i>=lef;i--)
{
sufmax[lvl][i] = vec[lvl][i];
if(i+1<=ri) sufmax[lvl][i]=max(sufmax[lvl][i+1], sufmax[lvl][i]);
}
for(int i=lef;i<=ri;i++)
{
prefmax[lvl][i] = vec[lvl][i]-(i-lef);
if(i>lef) prefmax[lvl][i]=max(prefmax[lvl][i-1],prefmax[lvl][i]);
}
return N;
}
void build(int id, int l, int r, int lvl=0)
{
st[id] = compute(lvl,l,r-1);
if(r-l<2) return ;
int mid=(l+r)>>1;
build(id*2,l,mid,lvl+1); build(id*2+1,mid,r,lvl+1);
}
vi query(int id, int l, int r, int ql, int qr) //get which nodes i need to care for my query
{
if(ql>=r||l>=qr) return {};
if(ql<=l&&r<=qr)
{
//cerr<<"NODE : "<<l<<' '<<r-1<<'\n';
return {id};
}
int mid=(l+r)>>1;
vi L=query(id*2,l,mid,ql,qr);
vi R=query(id*2+1,mid,r,ql,qr);
for(int x:R) L.pb(x);
return L;
}
const int DEBUG = 0;
int main()
{
//ios_base::sync_with_stdio(0); cin.tie(0);
if(!DEBUG)
{
scanf("%d",&n); scanf("%s",s);
}
if(DEBUG)
{
srand(time(NULL));
freopen("election_boi.in","w",stdout);
n=10;
for(int i=0;i<n;i++) s[i] = (rand()&1?'C':'T');
}
if(DEBUG) cout<<n<<'\n'<<s<<'\n';
int q;
if(!DEBUG) cin>>q;
if(DEBUG)
{
q=5;
cout<<q<<'\n';
}
build(1,0,n);
//outnode(st[1]);
for(int i=0;i<q;i++)
{
int l,r;
if(!DEBUG)
{
//cin>>l>>r;
scanf("%d %d",&l,&r);
l--; r--;
}
if(DEBUG)
{
l=rand()%n; r=rand()%n;
if(l>r) swap(l,r);
cout<<l+1<<' '<<r+1<<'\n';
}
vector<int> nodes = query(1,0,n,l,r+1);
int Lcnt = 0;
int Rcnt = 0;
int maxmiddle = 0;
int curL = 0; int minpref = 0;
for(int v:nodes)
{
//curL of the vec elements will be rekted
int badbrackets = st[v].len; int lvl = st[v].lvl; int l = st[v].l;
//cerr<<"BAD : "<<badbrackets<<' '<<lvl<<' '<<l<<'\n';
if(badbrackets==0)
{
minpref = max(st[v].lastneg, minpref - st[v].sum);
curL += st[v].sum;
}
else
{
if(curL>=badbrackets)
{
minpref = max(st[v].minprefback, minpref - st[v].sum);
curL-=badbrackets;
curL+=st[v].sum+badbrackets;
}
else
{
maxmiddle = max(maxmiddle, prefmax[lvl][l+curL] + curL);
maxmiddle = max(maxmiddle, minpref + curL);
Lcnt += badbrackets - curL;
if(curL+1<st[v].len) maxmiddle = max(maxmiddle, sufmax[lvl][l+curL+1]);
curL = st[v].sum + badbrackets;
minpref = st[v].lastneg;
}
}
/*
outnode(st[v]);
cerr<<"MINPREF : "<<minpref<<'\n';
cerr<<"CURL : "<<curL<<'\n';
cerr<<"LCNT : "<<Lcnt<<'\n';
cerr<<'\n';
*/
}
Rcnt = max(Rcnt, max(minpref, maxmiddle - curL));
int ans=Lcnt+Rcnt;
if(DEBUG)
{
if(ans!=solve_naive(l,r))
{
assert(0);
cerr<<"HERE"<<'\n';
}
cerr<<ans<<' '<<solve_naive(l,r)<<'\n';
}
else
{
//cout<<ans<<' '<<solve_naive(l,r)<<'\n';
printf("%d\n",ans);
}
//cout<<solve(l,r)<<'\n';
}
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:195:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n); scanf("%s",s);
~~~~~^~~~~~~~~
election.cpp:195:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n); scanf("%s",s);
~~~~~^~~~~~~~
election.cpp:200:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("election_boi.in","w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:220:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&l,&r);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1200 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1200 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1200 KB |
Output is correct |
| 6 |
Correct |
407 ms |
18456 KB |
Output is correct |
| 7 |
Correct |
415 ms |
18456 KB |
Output is correct |
| 8 |
Correct |
418 ms |
18456 KB |
Output is correct |
| 9 |
Correct |
371 ms |
18456 KB |
Output is correct |
| 10 |
Correct |
387 ms |
18456 KB |
Output is correct |
| 11 |
Correct |
443 ms |
19420 KB |
Output is correct |
| 12 |
Correct |
374 ms |
19420 KB |
Output is correct |
| 13 |
Correct |
359 ms |
19448 KB |
Output is correct |
| 14 |
Correct |
370 ms |
19448 KB |
Output is correct |
| 15 |
Correct |
535 ms |
19448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1200 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1200 KB |
Output is correct |
| 6 |
Correct |
407 ms |
18456 KB |
Output is correct |
| 7 |
Correct |
415 ms |
18456 KB |
Output is correct |
| 8 |
Correct |
418 ms |
18456 KB |
Output is correct |
| 9 |
Correct |
371 ms |
18456 KB |
Output is correct |
| 10 |
Correct |
387 ms |
18456 KB |
Output is correct |
| 11 |
Correct |
443 ms |
19420 KB |
Output is correct |
| 12 |
Correct |
374 ms |
19420 KB |
Output is correct |
| 13 |
Correct |
359 ms |
19448 KB |
Output is correct |
| 14 |
Correct |
370 ms |
19448 KB |
Output is correct |
| 15 |
Correct |
535 ms |
19448 KB |
Output is correct |
| 16 |
Execution timed out |
3052 ms |
101732 KB |
Time limit exceeded |
| 17 |
Halted |
0 ms |
0 KB |
- |
