#include "bits/stdc++.h"
using namespace std;
const int K=19;
int n, q;
// get INDEX of min in [l,r]
struct st{
vector<int> a;
vector<vector<int>> mn;
st(vector<int> a){
this->a=a;
mn.resize(K, vector<int>(n+1));
for(int i=1; i<=n; i++){
mn[0][i]=a[i];
}
for(int j=1; j<K; j++){
for(int i=0; i+(1<<j)<=n+1; i++){
mn[j][i]=min(mn[j-1][i], mn[j-1][i+(1<<(j-1))]);
}
}
}
int qry(int l, int r){
int v=1e9;
int i=l-1;
for(int k=0; k<K; k++){
if((r-l+2)&(1<<k)){
v=min(v, mn[k][i]);
i+=(1<<k);
}
}
// cout << "mn " << l << " " << r << " " << v << "\n";
i=l-1;
for(int k=K-1; k>=0; k--){
if(i+(1<<k)>r+1) continue;
if(mn[k][i]>v) i+=(1<<k);
}
return i;
}
};
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
vector<int> a(n+1), b(n+1);
for(int i=1; i<=n; i++){
char c; cin >> c;
a[i]=(c=='C'?1:-1);
}
for(int i=n; i>=1; i--){
b[i]=a[n+1-i];
}
for(int i=1; i<=n; i++){
a[i]+=a[i-1];
b[i]+=b[i-1];
}
st st1(a), st2(b);
cin >> q;
while(q--){
int l,r;
cin >> l >> r;
int i=st1.qry(l,r);
int j=n-st2.qry(n+1-r, n+1-l);
// cout << "ij " << i << " " << j << "\n";
if(i<j) cout << a[l-1]-a[i]+a[j]-a[r] << "\n";
else cout << a[j]-a[i]-min(a[r]-a[i], a[j]-a[l-1]) << '\n';
}
}
// when the lights are out like the love is gone
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
