#include <bits/stdc++.h>
#define vec vector
#define f first
#define s second
#define endl '\n'
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;
typedef pair<int,int> pii;
const int N=5e5+1;
int lwr[N];
int ans[N],x[N];
vec<pii>qry[N];
int mn[N][20];
int lvl[N];
vec<int>del[N];
bool is=0;
struct tr{
int sm=0;
int suf=2*N;
};
tr mg(tr a,tr b){
tr c;
c.sm=a.sm+b.sm;
c.suf=min({b.suf,a.suf+b.sm});
if(is) cout<<c.suf<<endl;
return c;
}
tr emp,t[4*N];
void upd(int id,int x,int v,int tl,int tr){
if(tl==tr){
t[v].sm=x;t[v].suf=x;
return;
}
int tm=(tl+tr)>>1;
if(tm>=id) upd(id,x,2*v,tl,tm);
else upd(id,x,2*v+1,tm+1,tr);
t[v]=mg(t[2*v],t[2*v+1]);
}
tr get(int l,int r,int v,int tl,int tr){
if(tl>=l && tr<=r) return t[v];
if(tl>r || tr<l) return emp;
int tm=(tl+tr)>>1;
return mg(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
}
int getmn(int l,int r){
int x=lvl[r-l+1];
return min(mn[l][x],mn[r-(1<<x)+1][x]);
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,q;
cin>>n;
vec<int>a(n+1);string s;
cin>>s;s.insert(s.begin(),'0');
for(int i=1;i<=n;i++){
a[i]=(i?a[i-1]:0)+(s[i]=='C'?1:-1);
x[i]=(s[i]=='C'?1:-1);
mn[i][0]=a[i];
}
for(int i=2;i<N;i++) lvl[i]=lvl[i/2]+1;
for(int j=1;j<20;j++){
for(int i=0;i+(1<<(j-1))<=n;i++){
mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
//cout<<i<<' '<<j<<' '<<mn[i][j]<<endl;
}
}
vec<pii>vc;
{
vc.pb({-2e9,-1});
for(int i=0;i<=n;i++){
while(sz(vc) && vc.back().f>a[i]) vc.pop_back();
lwr[i]=vc.back().s;
vc.pb({a[i],i});
}
}
cin>>q;
for(int i=0;i<q;i++){
int l,r;
cin>>l>>r;
qry[l].pb({r,i});
}
for(int i=0;i<=n;i++){
if(x[i]<0)del[lwr[i]+2].pb(i);
}
// int x=0;
for(int i=n;i>=1;i--){
int w=(x[i]<0?0:1);
upd(i,w,1,0,n);
cout<<"APLY "<<i<<' '<<1<<endl;
for(auto &z : qry[i]){
int l=i,r=z.f;
int answ=0;
answ+=max(0,-(getmn(l,r)-a[l-1]));
// cout<<get(l,r,1,0,n).suf<<endl;
answ-=min(0,get(l,r,1,0,n).suf);
ans[z.s]=answ;
}
for(auto &z : del[i]){
upd(z,-1,1,0,n);
// cout<<"APly "<<z<<' '<<-1<<endl;
}
}
for(int i=0;i<q;i++) cout<<ans[i]<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
26060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
26060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
26060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
