#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
const int inf = 2e9;
int a[N], p[N], n;
int st[4 * N], lzy[4 * N];
void Init(int node, int l, int r) {
if (l == r) {
st[node] = p[l];
return;
}
int mid = l + r >> 1;
Init(2 * node, l, mid);
Init(2 * node + 1, mid + 1, r);
st[node] = max(st[2 * node], st[2 * node + 1]);
}
void Propagate(int node, int l, int r) {
if (lzy[node] == 0) return;
if (l < r) {
lzy[2 * node] += lzy[node];
lzy[2 * node + 1] += lzy[node];
}
st[node] += lzy[node];
lzy[node] = 0;
}
void Add(int node, int l, int r, int ql, int qr, int x) {
Propagate(node, l, r);
if (r < ql || qr < l || ql > qr) return;
if (ql <= l && r <= qr) {
lzy[node] += x;
Propagate(node, l, r);
return;
}
int mid = l + r >> 1;
Add(2 * node, l, mid, ql, qr, x);
Add(2 * node + 1, mid + 1, r, ql, qr, x);
st[node] = max(st[2 * node], st[2 * node + 1]);
}
int Get(int node, int l, int r, int ql, int qr) {
Propagate(node, l, r);
if (r < ql || qr < l) return -inf;
if (ql <= l && r <= qr) return st[node];
int mid = l + r >> 1;
return max(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr));
}
vector<int> qq[N];
stack<int> stk;
void Do(int x) {
stk.push(x);
Add(1, 1, n, x, n, -1);
}
void Undo() {
if (stk.size() == 0) return;
int x = stk.top(); stk.pop();
Add(1, 1, n, x, n, 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
string s; cin >> s;
for (int i = 1; i <= n; i++) {
if (s[i - 1] == 'C') a[i] = -1;
else a[i] = 1;
p[i] = p[i - 1] + a[i];
}
Init(1, 1, n);
int q; cin >> q;
vector<int> l(q), r(q), ans(q);
for (int i = 0; i < q; i++) {
cin >> l[i] >> r[i];
qq[r[i]].push_back(i);
}
for (int i = 1; i <= n; i++) {
if (s[i - 1] == 'T') Do(i);
else Undo();
for (int j : qq[i]) {
int o = Get(1, 1, n, l[j], r[j]);
if (l[j] >= 2) o -= Get(1, 1, n, l[j] - 1, l[j] - 1);
ans[j] += stk.size() + max(o, 0);
}
}
for (int i = 0; i < q; i++) cout << ans[i] << en;
return 0;
}
Compilation message
election.cpp: In function 'void Init(int, int, int)':
election.cpp:18:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | int mid = l + r >> 1;
| ~~^~~
election.cpp: In function 'void Add(int, int, int, int, int, int)':
election.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid = l + r >> 1;
| ~~^~~
election.cpp: In function 'int Get(int, int, int, int, int)':
election.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
