#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const int N=2e5 + 5;
const ll oo = 1e9;
int n,a[N][2],i,t[4*N][2];
string s;
void build (int i, int l, int r){
if (l == r){
t[i][0] = a[l][0];
t[i][1] = a[l][1];
return;
}
int mid = (l + r)/2;
build (i*2, l, mid);
build (i*2 + 1, mid + 1, r);
t[i][0] = min (t[i * 2][0], t[i * 2 + 1][0]);
t[i][1] = min (t[i * 2][1], t[i * 2 + 1][1]);
}
int get (int k, int i, int l, int r, int u, int v){
if (l > v || r < u)
return oo;
if (l >= u && r <= v)
return t[i][k];
int mid = (l + r)/2;
return min (get(k, i * 2, l, mid, u , v), get (k,i * 2 + 1, mid + 1, r, u, v));
}
int q,l,r;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
cin >> s;
forr (i,1,n){
a[i][0] = a[i - 1][0];
a[n - i + 1][1] = a[n - i + 2][1];
if (s[i - 1] == 'C')
a[i][0]++;
else a[i][0]--;
if (s[n - i] == 'C')
a[n - i + 1][1]++;
else a[n - i + 1][1]--;
}
build (1,1,n);
cin >> q;
while (q--){
cin >> l >> r;
cout << abs (min((get(0,1,1,n,l,r) - a[l - 1][0]),get(1,1,1,n,l,r) - a[r + 1][1])) << "\n";
}
return 0;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
