#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;
int n;
string s;
vector < pii > query[N];
vector < int > stk;
int b[N];
struct TT {
int suf, sum;
TT() {}
};
struct T {
TT tree[N];
void upd(int pos, int val, int v = 1, int l = 1, int r = n) {
if (l == r) {
tree[v].sum = val;
tree[v].suf = min(val, 0);
return ;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
upd(pos, val, v + v, l, mid);
} else {
upd(pos, val, v + v + 1, mid + 1, r);
}
tree[v].sum = tree[v + v].sum + tree[v + v + 1].sum;
tree[v].suf = min(tree[v + v].suf + tree[v + v + 1].sum, tree[v + v + 1].suf);
}
pii get(int l, int r, int v = 1, int tl = 1, int tr = n) {
if (tl > r || tr < l) return mk(0, inf);
if (l <= tl && tr <= r) {
return mk(tree[v].sum, tree[v].suf);
}
int mid = (tl + tr) >> 1;
pii res1, res2;
res1 = get(l, r, v + v, tl, mid);
res2 = get(l, r, v + v + 1, mid + 1, tr);
return mk(res1.fr + res2.fr, min(res1.sc, res2.sc));
}
};
T tr;
void precalc() {
for (int i = 1; i <= n; i++) {
b[i] = ((s[i] == 'C') ? 1 : -1);
tr.upd(i, 1);
}
}
int ans[N];
main() {
scanf("%d", &n);
cin >> s;
s = " " + s;
precalc();
int q;
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int l, r;
scanf("%d %d", &l, &r);
query[l].pb(mk(r, i));
}
for (int i = n; i >= 1; i--) {
if (b[i] == -1) {
stk.pb(i);
tr.upd(i, 0);
b[i] = 0;
} else if (b[i] == 1) {
if (!stk.empty()) {
tr.upd(stk.back(), -1);
b[stk.back()] = -1;
stk.pop_back();
}
}
for (pii to : query[i]) {
// cout << upper_bound(stk.rbegin(), stk.rend(), to.fr) - stk.rbegin() << ' ' << tr.get(1, to.fr).sc << endl;
ans[to.sc] = upper_bound(stk.rbegin(), stk.rend(), to.fr) - stk.rbegin() - tr.get(1, to.fr).sc;
}
}
for (int i = 1; i <= q; i++) {
printf("%d\n", ans[i]);
}
}
Compilation message
election.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
election.cpp: In function 'int main()':
election.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
election.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
election.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &l, &r);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
12192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
12192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
12192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
