#include <bits/stdc++.h>
using namespace std;
#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>(aaaa-1))&1)
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<pair<int,int>,pair<int,int>> piiii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
typedef pair<long double,long double> pld;
typedef pair<pair<long double,long double>,long double> plld;
typedef pair<long double,long long> pdl;
const ll base=361;
const ll mod=1e9+7;
const ll mod2=1e9;
const ld eps=1e-3;
const ld eps2=1e-7;
const ll maxn=1e16;
const ld pi=acos(-1);
const ll delta=1e5+7;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
const int dxkn[8]={1,1,2,2,-1,-1,-2,-2};
const int dykn[8]={2,-2,1,-1,2,-2,1,-1};
const int dxki[8]={1,1,1,0,0,-1,-1,-1};
const int dyki[8]={1,0,-1,1,-1,1,0,-1};
struct segtree_ele{
int l,r,lrange,rrange,gt;
} segtree[4000009];
string s;
int a[2000009],pre[2000009],suf[2000009],n,i,q,l,r;
segtree_ele combine(int rl,int rr,segtree_ele l,segtree_ele r) {
segtree_ele kq;
kq.l=l.l;
kq.r=r.r;
kq.lrange=l.lrange;
kq.rrange=r.rrange;
int mid=(rr+rl)/2;
if (l.lrange==mid-rl+1) {
if (r.l>0) {
kq.l+=r.l;
kq.lrange+=r.lrange;
}
}
if (r.rrange==rr-mid) {
if (l.r>0) {
kq.r+=l.r;
kq.rrange+=l.rrange;
}
}
kq.gt=max(max(l.gt,r.gt),l.r+r.l);
return kq;
}
void init(int id,int l,int r) {
if (l!=r) {
int mid=(r+l)/2;
init(id*2,l,mid);
init(id*2+1,mid+1,r);
segtree[id]=combine(l,r,segtree[id*2],segtree[id*2+1]);
}
else {
segtree[id].l=a[l];
segtree[id].r=a[l];
segtree[id].gt=a[l];
segtree[id].lrange=1;
segtree[id].rrange=1;
}
//cout<<l<<' '<<r<<' '<<segtree[id].gt<<'\n';
}
segtree_ele get(int id,int l,int r,int u,int v) {
if (l>r||r<u||l>v) {
return {0,0,0,0,0};
}
if (u<=l&&r<=v) {
return segtree[id];
}
int mid=(r+l)/2;
return combine(l,r,get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int main(){
IO;
cin>>n;
cin>>s;
s=" "+s;
for (i=1;i<=n;i++) {
if (s[i]=='C') {
a[i]=1;
}
else {
a[i]=-1;
}
}
init(1,1,n);
for (i=1;i<=n;i++) {
pre[i]=pre[i-1];
if (s[i]=='C') {
pre[i]++;
}
else {
pre[i]--;
}
}
for (i=n;i>=1;i--) {
suf[i]=suf[i+1];
if (s[i]=='C') {
suf[i]++;
}
else {
suf[i]--;
}
}
cin>>q;
for (i=1;i<=q;i++) {
cin>>l>>r;
//cout<<get(1,1,n,l,r).gt<<' ';
cout<<-(pre[n]-pre[l-1]-suf[r+1]-max(0,get(1,1,n,l,r).gt))<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
