제출 #1093098

#제출 시각아이디문제언어결과실행 시간메모리
1093098juicyElection (BOI18_election)C++17
82 / 100
3064 ms42984 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif const int N = 5e5 + 5; int n, q; int res[N]; array<int, 2> tr[4 * N]; string s; vector<array<int, 2>> que[N]; array<int, 2> operator + (const array<int, 2> &lt, const array<int, 2> &rt) { return {min(rt[0], lt[0] + rt[1]), lt[1] + rt[1]}; } void upd(int i, int x, int id = 1, int l = 1, int r = n) { if (l == r) { tr[id] = {x, x}; return; } int m = (l + r) / 2; if (i <= m) { upd(i, x, id * 2, l, m); } else { upd(i, x, id * 2 + 1, m + 1, r); } tr[id] = tr[id * 2] + tr[id * 2 + 1]; } array<int, 2> qry(int u, int v, int id = 1, int l = 1, int r = n) { if (u <= l && r <= v) { return tr[id]; } int m = (l + r) / 2; if (v <= m) { return qry(u, v, id * 2, l, m); } if (m < u) { return qry(u, v, id * 2 + 1, m + 1, r); } return qry(u, v, id * 2, l, m) + qry(u, v, id * 2 + 1, m + 1, r); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> s >> q; for (int i = 1; i <= q; ++i) { int l, r; cin >> l >> r; que[l].push_back({r, i}); } vector<int> st; for (int i = n; i; --i) { if (s[i - 1] == 'T') { st.push_back(i); } else { upd(i, 1); if (st.size()) { upd(st.back(), -1); st.pop_back(); } } sort(que[i].begin(), que[i].end()); int k = st.size(); for (auto [j, id] : que[i]) { while (k - 1 >= 0 && st[k - 1] <= j) { --k; } res[id] = st.size() - k + max(0, -qry(i, j)[0]); } } for (int i = 1; i <= q; ++i) { cout << res[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...