Submission #1268343

#TimeUsernameProblemLanguageResultExecution timeMemory
1268343aegElection (BOI18_election)C++20
0 / 100
1 ms576 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t struct query { int l, r, id; query(int l, int r, int id) : l(l), r(r), id(id) {} }; bool operator<(query const &a, query const &b) { return a.l > b.l; } struct segtr { struct node { int tot, suf; node(int tot = 0, int suf = 0) : tot(tot), suf(suf) {} }; vector<node> tree; void build(int ind, int l, int r, vector<int> const &a) { if (l == r) { tree[ind].tot = a[l]; tree[ind].suf = min(int(0), a[l]); return; } int m = (l + r) >> 1; build(ind << 1, l, m, a); build(ind << 1 | 1, m + 1, r, a); tree[ind].tot = tree[ind << 1].tot + tree[ind << 1 | 1].tot; tree[ind].suf = min(tree[ind << 1].suf + tree[ind << 1 | 1].tot, tree[ind << 1 | 1].suf); } segtr(vector<int> const &a) : tree(a.size() << 2) { build(1, 0, a.size() - 1, a); } pair<int, int> query(int ind, int l, int r, int tl, int tr) { if (tl <= l && tr >= r) return {tree[ind].suf, tree[ind].tot}; if (tl > r || tr < l) return {INT32_MAX, 0}; int m = (l + r) >> 1; pair<int, int> a = query(ind << 1, l, m, tl, tr), b = query(ind << 1 | 1, m + 1, r, tl, tr); return {min(a.first + b.second, b.first), a.second + b.second}; } void update(int ind, int l, int r, int i, int val) { if (i > r || i < l) return; if (l == r) { tree[ind].tot = val; tree[ind].suf = min(val, int(0)); return; } int m = (l + r) >> 1; update(ind << 1, l, m, i, val); update(ind << 1 | 1, m + 1, r, i, val); tree[ind].tot = tree[ind << 1].tot + tree[ind << 1 | 1].tot; tree[ind].suf = min(tree[ind << 1].suf + tree[ind << 1 | 1].tot, tree[ind << 1 | 1].suf); } }; signed main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { char c; cin >> c; if (c == 'C') a[i] = 1; else a[i] = -1; } int q; cin >> q; vector<query> quer; for (int i = 0; i < q; i++) { int l, r; cin >> l >> r; l--; r--; quer.emplace_back(l, r, i); } vector<int> anses(q, 0); sort(quer.begin(), quer.end()); segtr tr(a); vector<int> st; int curind = n; for (int i = 0; i < q; i++) { while (curind > quer[i].l) { curind--; if (a[curind] == 1) { if (!st.empty()) { tr.update(1, 0, n - 1, st.back(), -1); st.pop_back(); } } else { tr.update(1, 0, n - 1, curind, 0); st.push_back(curind); } } int ans = upper_bound(st.begin(), st.end(), quer[i].r) - st.begin(); ans += -tr.query(1, 0, n - 1, quer[i].l, quer[i].r).first; anses[quer[i].id] = ans; } copy(anses.begin(), anses.end(), ostream_iterator<int>(cout, "\n")); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...