| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 918942 | myst6 | Election (BOI18_election) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h> using namespace std; struct Tree { vector<int> info, tags; Tree(int size) { info.resize(size*4, 0); tags.resize(size*4); } void pushdown(int x) { info[x] += tags[x]; if (x*2 < tags.size()) tags[x*2] += tags[x]; if (x*2+1 < tags.size()) tags[x*2+1] += tags[x]; tags[x] = 0; } void update(int l, int r, int x, int xl, int xr, int tag) { if (l > r) return; if (l == xl && r == xr) { tags[x] += tag; } else { int xm = (xl+xr)/2; update(l, min(r,xm), x*2, xl, xm, tag); update(max(l,xm+1), r, x*2+1, xm+1, xr, tag); pushdown(x*2); pushdown(x*2+1); info[x] = min(info[x*2], info[x*2+1]); } } int query(int l, int r, int x, int xl, int xr) { if (l > r) return 1<<30; pushdown(x); if (l == xl && r == xr) { return info[x]; } else { int xm = (xl+xr)/2; int left = query(l, min(r,xm), x*2, xl, xm); int right = query(max(l,xm+1), r, x*2+1, xm+1, xr); return min(left, right); } }}; struct BIT { vector<int> data; BIT(int size) { data.resize(size+1); } void update(int x, int delta) { while (x < data.size()) { data[x] += delta; x += x & (-x); } } int query(int x) { int ans = 0; while (x > 0) { ans += data[x]; x -= x & (-x); } return ans; }}; int main() { cin.tie(0)->sync_with_stdio(0); int N; cin >> N; string s; cin >> s; int Q; cin >> Q; vector<pair<int,int>> queries(Q); for (int i=0; i<Q; i++) { int L, R; cin >> L >> R; queries[i] = {L-1, R-1}; } vector<int> order(Q); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int i, int j) -> bool { return queries[i].first > queries[j].first; }); int L = N-1; set<int> Xs; BIT left(N); Tree right(N); vector<int> ans(Q); for (int i=0; i<Q; i++) { pair<int,int> q = queries[order[i]]; while (L >= q.first) { if (s[L] == 'C') { if (!Xs.empty()) { int idx = *Xs.begin(); left.update(idx+1, -1); right.update(0, idx, 1, 0, N-1, -1); Xs.erase(idx); } right.update(0, L, 1, 0, N-1, +1); } else { Xs.insert(L); left.update(L+1, +1); } L -= 1; } int R = q.second; int base = left.query(R+1); int extra = right.query(L+1, R, 1, 0, N-1); int next = R == N-1 ? 0 : right.query(R+1, R+1, 1, 0, N-1); ans[order[i]] = base - min(0, extra - next); } for (int i=0; i<Q; i++) { cout << ans[i] << "\n"; } return 0;}