#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 5e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}
int n,q,M[4*maxn][3],T[4*maxn][3],ans[maxn];
string s;
queue<int>last;
void prop(int tp,int nd){
if(tp==0){
T[nd*2][0] += T[nd][1];
T[nd*2][1] += T[nd][1];
T[nd*2+1][0] += T[nd][1];
T[nd*2+1][1] += T[nd][1];
T[nd][1] = 0;
}
else {
M[nd*2][0] += M[nd][1];
M[nd*2][1] += M[nd][1];
M[nd*2+1][0] += M[nd][1];
M[nd*2+1][1] += M[nd][1];
M[nd][1] = 0;
}
}
void upd(int val,int a,int b,int l,int r,int nd){
if(r < a or l > b) return;
if(l >= a and r <= b){T[nd][0] += val,T[nd][1] += val;return;}
prop(0,nd);
upd(val,a,b,l,(l+r)/2,nd*2);
upd(val,a,b,(l+r)/2+1,r,nd*2+1);
T[nd][0]=min(T[nd*2][0],T[nd*2+1][0]);
}
int tap(int a,int b,int l,int r,int nd){
if(r < a or l > b) return mod;
if(l >= a and r <= b) return T[nd][0];
prop(0,nd);
return min(tap(a,b,l,(l+r)/2,nd*2),tap(a,b,(l+r)/2+1,r,nd*2+1));
}
void upd1(int val,int a,int b,int l,int r,int nd){
if(r < a or l > b) return;
if(l >= a and r <= b){M[nd][0] += val,M[nd][1] += val;return;}
prop(1,nd);
upd1(val,a,b,l,(l+r)/2,nd*2);
upd1(val,a,b,(l+r)/2+1,r,nd*2+1);
M[nd][0]=max(M[nd*2][0],M[nd*2+1][0]);
}
int tap1(int a,int b,int l,int r,int nd){
if(r < a or l > b) return 0;
if(l >= a and r <= b) return M[nd][0];
prop(1,nd);
return max(tap1(a,b,l,(l+r)/2,nd*2),tap1(a,b,(l+r)/2+1,r,nd*2+1));
}
int main(){
#ifdef LOCAL
clock_t TSTART = clock();
#endif
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s >> q;
vector<pii>v[n];
int a,b;
for(int i = 0;i < q;i++){
cin >> a >> b;
v[a-1].pb({b-1,i});
}
// for(int i = n-1;i >= 0;i--){
// if(sz(v[i])){
// cout<<i<<" ---> ";
// for(auto j : v[i]) cout<<j.ff<<' ';
// cout<<'\n';
// }
// }
for(int i = n-1;i >= 0;i--){
if(s[i]=='C'){
upd(1,i,n-1,0,n-1,1);
upd1(1,i,n-1,0,n-1,1);
if(!last.empty()){
int pos=last.front();
last.pop();
upd1(-1,pos,n-1,0,n-1,1);
}
}
else {
upd(-1,i,n-1,0,n-1,1);
last.push(i);
}
for(auto j : v[i]){
a = tap(i,j.ff,0,n-1,1);
b = tap1(i,j.ff,0,n-1,1);
int val = tap(j.ff,j.ff,0,n-1,1) - a;
// cout<<a<<' '<<b<<' '<<val<<'\n';
ans[j.ss]=b-val-min(0,a);
}
}
for(int i = 0;i < q;i++) cout<<ans[i]<<'\n';
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()-TSTART) / CLOCKS_PER_SEC << " s.\n";
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
