#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;
const int len = 5e5+5, inf = 1e9;
int out[len], tree[4*len], lazy[4*len], pref[len], arr[len];
ii ask[len];
char str[len];
vector<int> st, vec[len];
void build(int p, int l, int r){
if (l == r)
tree[p] = pref[l], lazy[p] = 0;
else{
int mid = (l+r)/2;
build(2*p, l, mid);
build(2*p+1, mid+1, r);
tree[p] = min(tree[2*p], tree[2*p+1]);
lazy[p] = 0;
}
}
void prop(int p, int l, int r){
if (lazy[p] == 0) return;
tree[p] += lazy[p];
if (l != r){
lazy[2*p] += lazy[p];
lazy[2*p+1] += lazy[p];
}
lazy[p] = 0;
}
void update(int p, int l, int r, int i, int j, int v){
prop(p, l, r);
if (i <= l && r <= j)
lazy[p] += v;
else if (r < i || j < l)
return;
else{
int mid = (l+r)/2;
update(2*p, l, mid, i, j, v);
update(2*p+1, mid+1, r, i, j, v);
prop(2*p, l, mid);
prop(2*p+1, mid+1, r);
tree[p] = min(tree[2*p], tree[2*p+1]);
}
}
int query(int p, int l, int r, int i, int j){
prop(p, l, r);
if (i <= l && r <= j)
return tree[p];
if (r < i || j < l)
return inf;
int mid = (l+r)/2;
return min(query(2*p, l, mid, i, j), query(2*p+1, mid+1, r, i, j));
}
int bs(int x){
int l = 0, r = (int)st.size()-1, ans = (int)st.size();
while (l <= r){
int mid = (l+r)/2;
if (st[mid] >= x)
ans = mid, r = mid-1;
else
l = mid+1;
}
return ans;
}
int main(){
int n, q;
scanf("%d %s", &n, &str);
for (int i = 1; i <= n; i++){
if (str[i-1] == 'C') arr[i] = 1;
else arr[i] = -1;
pref[i] = pref[i-1] + arr[i];
}
build(1, 1, n);
scanf("%d", &q);
for (int i = 0; i < q; i++){
scanf("%d %d", &ask[i].fi, &ask[i].se);
vec[ask[i].se].pb(i);
}
for (int i = 1; i <= n; i++){
if (arr[i] == 1 && !st.empty()){
update(1, 1, n, st.back(), n, -1);
st.pop_back();
}
if (arr[i] == -1){
update(1, 1, n, i, n, +1);
st.pb(i);
}
for (int j = 0; j < vec[i].size(); j++){
int l = ask[vec[i][j]].fi, r = i, lef = bs(l), rig = st.size()-lef;
//if (i == 17){
// printf("l = %d, r = %d, lef = %d, rig = %d\n", l, r, lef, rig);
//printf("mn = %d\n", query(1, 1, n, l, r) - pref[l-1] - lef);
//}
out[vec[i][j]] = rig - min(0, query(1, 1, n, l, r)-pref[l-1]-lef);
}
}
for (int i = 0; i < q; i++)
printf("%d\n", out[i]);
return 0;
}
/*
17
TTCTTCCCTCTTTTCTC
1
14 17
*/
Compilation message
election.cpp: In function 'int main()':
election.cpp:82:28: warning: format '%s' expects argument of type 'char*', but argument 3 has type 'char (*)[500005]' [-Wformat=]
scanf("%d %s", &n, &str);
~~~~^
election.cpp:108:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec[i].size(); j++){
~~^~~~~~~~~~~~~~~
election.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %s", &n, &str);
~~~~~^~~~~~~~~~~~~~~~~~~
election.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
election.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &ask[i].fi, &ask[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
12212 KB |
Output is correct |
| 2 |
Correct |
18 ms |
12272 KB |
Output is correct |
| 3 |
Correct |
16 ms |
12508 KB |
Output is correct |
| 4 |
Correct |
20 ms |
12656 KB |
Output is correct |
| 5 |
Correct |
15 ms |
12676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
12212 KB |
Output is correct |
| 2 |
Correct |
18 ms |
12272 KB |
Output is correct |
| 3 |
Correct |
16 ms |
12508 KB |
Output is correct |
| 4 |
Correct |
20 ms |
12656 KB |
Output is correct |
| 5 |
Correct |
15 ms |
12676 KB |
Output is correct |
| 6 |
Correct |
146 ms |
18588 KB |
Output is correct |
| 7 |
Correct |
120 ms |
18848 KB |
Output is correct |
| 8 |
Correct |
135 ms |
19864 KB |
Output is correct |
| 9 |
Correct |
136 ms |
21172 KB |
Output is correct |
| 10 |
Correct |
141 ms |
22120 KB |
Output is correct |
| 11 |
Correct |
201 ms |
23324 KB |
Output is correct |
| 12 |
Correct |
132 ms |
24144 KB |
Output is correct |
| 13 |
Correct |
132 ms |
25372 KB |
Output is correct |
| 14 |
Correct |
135 ms |
26040 KB |
Output is correct |
| 15 |
Correct |
132 ms |
26860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
12212 KB |
Output is correct |
| 2 |
Correct |
18 ms |
12272 KB |
Output is correct |
| 3 |
Correct |
16 ms |
12508 KB |
Output is correct |
| 4 |
Correct |
20 ms |
12656 KB |
Output is correct |
| 5 |
Correct |
15 ms |
12676 KB |
Output is correct |
| 6 |
Correct |
146 ms |
18588 KB |
Output is correct |
| 7 |
Correct |
120 ms |
18848 KB |
Output is correct |
| 8 |
Correct |
135 ms |
19864 KB |
Output is correct |
| 9 |
Correct |
136 ms |
21172 KB |
Output is correct |
| 10 |
Correct |
141 ms |
22120 KB |
Output is correct |
| 11 |
Correct |
201 ms |
23324 KB |
Output is correct |
| 12 |
Correct |
132 ms |
24144 KB |
Output is correct |
| 13 |
Correct |
132 ms |
25372 KB |
Output is correct |
| 14 |
Correct |
135 ms |
26040 KB |
Output is correct |
| 15 |
Correct |
132 ms |
26860 KB |
Output is correct |
| 16 |
Correct |
1051 ms |
58304 KB |
Output is correct |
| 17 |
Correct |
774 ms |
61456 KB |
Output is correct |
| 18 |
Correct |
948 ms |
71040 KB |
Output is correct |
| 19 |
Correct |
906 ms |
80768 KB |
Output is correct |
| 20 |
Correct |
1106 ms |
87212 KB |
Output is correct |
| 21 |
Correct |
1408 ms |
97236 KB |
Output is correct |
| 22 |
Correct |
1124 ms |
104568 KB |
Output is correct |
| 23 |
Correct |
1189 ms |
113076 KB |
Output is correct |
| 24 |
Correct |
1088 ms |
120176 KB |
Output is correct |
| 25 |
Correct |
996 ms |
127060 KB |
Output is correct |
