#include <bits/stdc++.h>
#define all(v) ((v).bvin(),(v).end())
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 8e6 + 1;
struct tree{
int Cdec,Cinc,Tdec,Tinc,Pinc,Pdec,Pall,Tnum;
};
tree seg[mxN];
int N,s,e;
tree combine(tree a, tree b){
tree c;
c.Tnum = a.Tnum + b.Tnum;
c.Cinc = max(a.Cinc - b.Tinc,0) + b.Cinc;
c.Cdec = max(b.Cdec - a.Tdec,0) + a.Cdec;
c.Tinc = max(b.Tinc - a.Cinc,0) + a.Tinc;
c.Tdec = max(a.Tdec - b.Cdec,0) + b.Tdec;
c.Pinc = a.Pinc + b.Pinc + min(a.Cinc,b.Tinc);
c.Pdec = b.Pdec + a.Pdec + min(b.Cdec,a.Tdec);
c.Pall = min(a.Pinc + min({a.Cinc,max((b.Tinc - b.Tdec),0)}) + b.Pall,b.Pdec + min({b.Cdec,max((a.Tdec - a.Tinc),0)}) + a.Pall) ;
return c;
}
tree query(int l = 1,int r = N,int ind = 1){
if(l > e || r < s) return {0,0,0,0,0,0,0};
if(l >= s && r <= e) return seg[ind];
int md = (l + r) / 2;
return combine(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void printseg(){
int p2 = 1;
for(int i = 1;i <= N * 2 - 1;i++){
cout<<'{'<<seg[i].Cinc<<','<<seg[i].Cdec<<','<<seg[i].Tinc<<','<<seg[i].Tdec<<','<<seg[i].Tnum<<','<<seg[i].Pinc<<','<<seg[i].Pdec<<','<<seg[i].Pall<<"} ";
if(i == p2 * 2 - 1){
cout<<'\n';
p2 *= 2;
}
}
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,q;
string s;
cin >>n>>s>>q;
N = exp2(ceil(log2(n)));
for(int i = 0;i < n;i++){
if(s[i] == 'C'){
seg[i + N].Cinc = 1;
seg[i + N].Cdec = 1;
}else{
seg[i + N].Tinc = 1;
seg[i + N].Tdec = 1;
seg[i + N].Tnum = 1;
}
}
for(int i = N - 1;i;i--){
seg[i] = combine(seg[i * 2],seg[i * 2 + 1]);
}
// printseg();
while(q--){
cin>>s>>e;
tree qe = query();
cout<<qe.Tnum - qe.Pall<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
