#include <bits/stdc++.h>
using namespace std;
constexpr int M = 500'005;
constexpr int base = 500'005;
pair<int, int> tree[2][base*2]; //od przodu, od tyłu
int lewo[M];
int prawo[M];
pair<int, int> query(int a, int b, int v2){
a = a + base - 1;
b = b + base + 1;
pair<int, int> wynik = {21376969, 0};
while(a/2!=b/2){
if(a%2==0 && wynik.first > tree[v2][a+1].first) wynik = tree[v2][a+1];
if(b%2==1 && wynik.first > tree[v2][b-1].first) wynik = tree[v2][b-1];
a/=2, b/=2;
}
return wynik;
}
void add(int v, int x, int v2){
tree[v2][v + base].second = v;
v = v + base;
tree[v2][v].first += x;
v/=2;
while(v){
if(tree[v2][v*2].first < tree[v2][v*2+1].first) tree[v2][v] = tree[v2][v*2];
else tree[v2][v] = tree[v2][v*2+1];
v/=2;
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n;
cin>>n;
string s;
cin>>s;
for(int i=1; i<=n; i++){
lewo[i] = lewo[i-1];
if(s[i-1]=='C') lewo[i]++;
else lewo[i]--;
}
for(int i=n; i>=1; i--){
prawo[i] = prawo[i+1];
if(s[i-1]=='C') prawo[i]++;
else prawo[i]--;
}
for(int i=1; i<=n; i++){
add(i, lewo[i], 0);
add(i, prawo[i], 1);
}
int k;
cin>>k;
while(k--){
int a, b;
cin>>a>>b;
int odPrawej = prawo[b];
int odLewej = lewo[a];
if(s[b-1]=='C') odPrawej = odPrawej - 1;
else odPrawej = odPrawej + 1;
if(s[a-1]=='C') odLewej = odLewej - 1;
else odLewej = odLewej + 1;
//cout<<odLewej<<" "<<odPrawej<<endl;
pair<int, int> minLewo = query(a, b, 0);
minLewo.first -= odLewej;
//cout<<minLewo.first<<" "<<minLewo.second<<endl;
pair<int, int> minPrawo1 = query(a, minLewo.second, 1);
pair<int, int> minPrawo2 = query(minLewo.second+1, b, 1);
pair<int, int> minPrawo;
minLewo.first = min(0, minLewo.first);
if(minPrawo1.first + minLewo.first*-1 < minPrawo2.first) minPrawo.first = minPrawo1.first + minLewo.first*-1;
else minPrawo = minPrawo2;
//cout<<minPrawo1.first<<" "<<minPrawo1.second<<endl;
//cout<<minPrawo2.first<<" "<<minPrawo2.second<<endl;
minPrawo.first -= odPrawej;
minPrawo.first = min(0, minPrawo.first);
cout<<minLewo.first*-1 + minPrawo.first*-1<<endl;
//cout<<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
