#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//1 => l-1~r
ll n,q,a[500100];
string s;
typedef struct leaf{
ll minind,maxind;
}leaf;
vector<leaf> tree = vector<leaf>(2000100);
void init(ll l,ll r,ll ind)
{
if(l==r)
{
tree[ind].minind = tree[ind].maxind = l;
return;
}
init(l,(l+r)/2,ind*2);
init((l+r)/2+1,r,ind*2+1);
tree[ind].minind = a[tree[ind*2].minind]>=a[tree[ind*2+1].minind]?tree[ind*2+1].minind:tree[ind*2].minind;
tree[ind].maxind = a[tree[ind*2].maxind]<=a[tree[ind*2+1].maxind]?tree[ind*2+1].maxind:tree[ind*2].maxind;
}
leaf query(ll l,ll r,ll s,ll e,ll ind)
{
if(s<=l&&r<=e)
return tree[ind];
if(e<l||r<s)
{
leaf ret;
ret.minind = ret.maxind = -1;
return ret;
}
leaf r1=query(l,(l+r)/2,s,e,ind*2);
leaf r2=query((l+r)/2+1,r,s,e,ind*2+1);
leaf ret;
if(r1.minind==-1)
return r2;
if(r2.minind==-1)
return r1;
ret.minind = a[r1.minind]>=a[r2.minind]?r2.minind:r1.minind;
ret.maxind = a[r1.maxind]<=a[r2.maxind]?r2.maxind:r1.maxind;
return ret;
}
ll ans(ll l,ll r)
{
leaf t = query(0,n,l,r,1);
ll b = a[t.maxind]-a[r];
ll av = a[l]-a[t.minind];
leaf t2 = query(0,n,l,t.maxind,1);
leaf t3 = query(0,n,t.minind,r,1);
ll c = a[l]-a[t2.minind];
ll d = a[t3.maxind]-a[r];
return c+d+max(b-d,av-c);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
cin>>s;
for(ll i=0;i<n;i++)
{
if(s[i]=='C')
a[i+1] = a[i]+1;
else
a[i+1] = a[i]-1;
}
init(0,n,1);
cin>>q;
while(q--)
{
ll l,r;
cin>>l>>r;
cout<<ans(l-1,r)<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
31572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
31572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
31572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
