#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
const int lim=5e5+5;
#else
const int lim=3e3+3;
#endif
#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define pb push_back
const int mod=998244353;
//const int mod=(1ll<<61)-1;
using pii=pair<int,int>;
struct Node{
int sum,pref,suf;
inline Node():sum(0),pref(0),suf(0){}
inline Node(int val):sum(val),pref(min<int>(0,val)),suf(pref){}
inline Node(int sum,int pref,int suf):sum(sum),pref(pref),suf(suf){}
};
struct segtree{
Node tree[4*lim];
int n,*p;
segtree(int n,int*p):n(n),p(p){
build(1,n,1);
//debug(1,n,1);
}
inline void debug(int l,int r,int node){
cout<<"[ "<<l<<", "<<r<<" ] "<<tree[node].sum<<" "<<tree[node].pref<<" "<<tree[node].suf<<"\n";
if(l^r){
int mid=(l+r)>>1,child=node<<1;
debug(l,mid,child),debug(mid+1,r,child|1);
}
if(node==1)cerr<<"\n";
}
inline Node merge(Node v1,Node v2){
return Node(
v1.sum+v2.sum,
min(v1.pref,v1.sum+v2.pref),
min(v2.suf,v2.sum+v1.suf)
);
}
inline Node build(int l,int r,int node){
if(l==r){
return tree[node]=Node(p[l]);
}
int mid=(l+r)>>1,child=node<<1;
return tree[node]=merge(build(l,mid,child),build(mid+1,r,child|1));
}
int P,VAL;
inline void update(int l,int r,int node){
if(l==r){
tree[node]=Node(VAL);
return;
}
int mid=(l+r)>>1,child=node<<1;
if(P<=mid)update(l,mid,child);
else update(mid+1,r,child|1);
tree[node]=merge(tree[child],tree[child|1]);
//cout<<"update: [ "<<l<<", "<<r<<" ] "<<tree[node].sum<<" "<<tree[node].pref<<" "<<tree[node].suf<<"\n";
}
inline void update(int p,int val){
P=p,VAL=val;
update(1,n,1);
}
int L,R;
inline Node query(int l,int r,int node){
if(L<=l&&r<=R){
return tree[node];
}
if(r<L||R<l){
return Node(0,INT_MAX,INT_MAX);
}
int mid=(l+r)>>1,child=node<<1;
return merge(query(l,mid,child),query(mid+1,r,child|1));
}
inline int query(int l,int r){
L=l,R=r;
Node res=query(1,n,1);
return max<int>(0,-res.suf);
}
int K;
inline int firstneg(int l,int r,int node){
//cout<<K<<"\n";
//cout<<"[ "<<l<<", "<<r<<" ] "<<tree[node].sum<<" "<<tree[node].pref<<" "<<tree[node].suf<<"\n";
if(l==r){
return l;
}
int mid=(l+r)>>1,child=node<<1;
if(tree[child].pref+K<0)return firstneg(l,mid,child);
K+=tree[child].sum;
return firstneg(mid+1,r,child|1);
}
inline int firstneg(){
if(0<=tree[1].pref){
return -1;
}
return firstneg(1,n,1);
}
};
inline void solve(){
int n;
cin>>n;
string s;
cin>>s;
int p[n+1];
p[0]=0;
for(int i=0;i<n;i++){
p[i+1]=(s[i]=='C')?1:-1;
}
int pr[n+1];
pr[0]=0;
for(int i=1;i<=n;i++){
pr[i]=pr[i-1]+p[i];
}
int q;
cin>>q;
vector<pii>a[n+1];
for(int i=0;i<q;i++){
int l,r;
cin>>l>>r;
a[l].pb(pii(r,i));
}
segtree st(n,p);
deque<int>have;
int to;
while(~(to=st.firstneg())){
have.pb(to);
st.update(to,0);
}
int ans[q];
for(int i=1;i<=n;i++){
while(have.size()&&0<pr[have.front()]-pr[i-1]){
st.update(have.front(),-1);
have.pop_front();
}
for(pii j:a[i]){
int l=0,r=have.size()-1,aaa=0;
while(l<=r){
int mid=(l+r)>>1;
if(have[mid]==j.first){
aaa=mid+1;
break;
}else if(have[mid]<j.first){
l=aaa=mid+1;
}else{
r=mid-1;
}
}
ans[j.second]=aaa+st.query(i,j.first);
}
st.update(i,0);
if(p[i]==1){
if(~(to=st.firstneg())){
have.push_front(to);
st.update(to,0);
}
}else if(have.size()&&have.front()==i){
have.pop_front();
}
/*
for(int i:have)cout<<i<<" ";
cout<<"\n";
*/
}
for(int i=0;i<q;i++){
cout<<ans[i]<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#else
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
47452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
47452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
47452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
