#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 lft[N],rgt[N];///for mx
int lwr[N];
int ans[N];
vec<pii>qry[N];
int mn[N][20];
int lvl[N];
int t[4*N],p1[4*N],p2[4*N];
void apply(int v,int x){
t[v]=x;p1[v]=x;p2[v]=0;
}
void add(int v,int x){
t[v]+=x;
if(p1[v]!=2e9){
p1[v]+=x;
}
else{
p2[v]+=x;
}
}
void push(int v,int tl,int tr){
if(tl==tr) return;
if(p1[v]!=2e9){
for(auto &u : {2*v,2*v+1}){
apply(u,p1[v]);
}
p1[v]=2e9;
}
if(p2[v]){
for(auto &u : {2*v,2*v+1}){
add(u,p2[v]);
}
p2[v]=0;
}
}
void upd(int l,int r,int tt,int x,int v,int tl,int tr){
for(int i=l;i<=r;i++){
if(tt==0) t[i]=x;
else t[i]+=x;
}
}
int get(int id,int v,int tl,int tr){
return t[id];
}
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);
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();
lft[i]=vc.back().s;
vc.pb({a[i],i});
}
}
vc.clear();
{
vc.pb({2e9,n+1});
for(int i=n;i>=0;i--){
while(sz(vc) && vc.back().f<a[i]) vc.pop_back();
rgt[i]=vc.back().s;
vc.pb({a[i],i});
}
}
vc.clear();
{
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[r].pb({l,i});
}
fill(p1,p1+4*N,2e9);
for(int i=1;i<=n;i++){
///i need maximum right such that pref[i-1]>pref[r]
upd(lft[i-1]+2,i,0,a[i-1],1,0,n);
// cout<<"APPLY "<<lft[i]+2<<' '<<i+1<<' '<<a[i]<<endl;
/// i'm in it if l<=i and pref[i]-pref[l-1]<0 lwr[i]>=l(maybe)
// cout<<lwr[i]+2<<' '<<i-1
upd(lwr[i]+2,i,1,-1,1,0,n);
//cout<<"ADD "<<lwr[i]+2<<' '<<i<<' '<<-1<<endl;
for(auto &z : qry[i]){
int l=z.f,r=i;
int m=a[r-1];int id=r;
for(int j=r;j>=l;j--){
if(m<a[j-1]){
m=a[j-1];id=j;
}
}
int answ=0;
answ+=max(0,-(getmn(l,r)-a[l-1]));
int x=m;
for(int i=id;i<=r;i++){
if(lwr[i]<l-1){
x--;
// cout<<"I "<<i<<endl;
}
}
//cout<<get(l,1,0,n)<<' '<<x<<endl;
// assert(get(l,1,0,n)<=x);
//cout<<"MN "<<getmn(l,r)<<' '<<a[l-1]<<endl;
answ-=min(0,a[r]-get(l,1,0,n));
ans[z.s]=answ;
}
}
for(int i=0;i<q;i++) cout<<ans[i]<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
22092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
22092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
22092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
