#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
// aintul interativ e baza.. poate ca nu
struct SegmTree {
struct Node {
int sum, min_suf;
Node(int val = 0) : sum(val), min_suf(min(0, val)) {}
Node(int sum_, int min_suf_) : sum(sum_), min_suf(min_suf_) {}
};
int n;
vector<Node> tree;
SegmTree(int n_) : n(n_), tree(4 * n) {}
Node Join(Node l, Node r) {
return {l.sum + r.sum,
min(l.min_suf + r.sum, r.min_suf)};
}
void Update(int node, int left, int right, int pos, int val) {
if (left == right) {
tree[node] = Node(val);
return;
}
int mid = left + (right - left) / 2;
if (pos <= mid) {
Update(2 * node + 1, left, mid, pos, val);
} else {
Update(2 * node + 2, mid + 1, right, pos, val);
}
tree[node] = Join(tree[2 * node + 1], tree[2 * node + 2]);
}
void Update(int pos, int val) {
Update(0, 0, n - 1, pos, val);
}
Node Query(int node, int left, int right, int x, int y) {
if (x <= left && right <= y) {
return tree[node];
}
int mid = left + (right - left) / 2;
Node l, r;
if (y <= mid) {
return Query(2 * node + 1, left, mid, x, y);
}
if (x > mid) {
return Query(2 * node + 2, mid + 1, right, x, y);
}
return Join(Query(2 * node + 1, left, mid, x, y),
Query(2 * node + 2, mid + 1, right, x, y));
}
int Query(int l, int r) {
return min(Query(0, 0, n - 1, l, r).min_suf, 0);
}
// void Update(int pos, int val) {
// for (tree[pos += n] = Node(val); pos /= 2; ) {
// tree[pos] = Join(tree[2 * pos], tree[2 * pos + 1]);
// }
// }
// int Query(int l, int r) {
// ++r;
// Node ans_left, ans_right;
// for (l += n, r += n; l < r; l /= 2, r /= 2) {
// if (l & 1) ans_left = Join(ans_left, tree[l++]);
// if (r & 1) ans_right = Join(tree[--r], ans_right);
// }
// return Join(ans_left, ans_right).min_suf;
// }
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n; cin.get();
string s; getline(cin, s);
int q; cin >> q;
vector<vector<pair<int, int>>> qrs(n);
for (int i = 0; i < q; ++i) {
int l, r; cin >> l >> r; --l, --r;
// dbg() name(l) name(r) endl;
qrs[l].emplace_back(i, r);
}
SegmTree st(n);
vector<int> ans(q), stk;
for (int i = n - 1; i >= 0; --i) {
int x = s[i] == 'C' ? +1 : -1;
if (x == 1) {
if (!stk.empty()) {
st.Update(stk.back(), -1);
stk.pop_back();
}
st.Update(i, x);
}
if (x == -1) {
stk.emplace_back(i);
}
// dbg() name(i) "stk: " << endl;
// for (auto &x : stk) dbg() x << ' '; dbg() endl;
for (auto &p : qrs[i]) {
int idx, r; tie(idx, r) = p;
ans[idx] = upper_bound(stk.rbegin(), stk.rend(), r) - stk.rbegin();
// dbg() name(idx + 1) name(ans[idx]) endl;
ans[idx] -= st.Query(i, r);
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
