Submission #935854

#TimeUsernameProblemLanguageResultExecution timeMemory
935854SamNguyenElection (BOI18_election)C++14
100 / 100
499 ms52052 KiB
#include <bits/stdc++.h> using namespace std; struct Node { int sum, rems; Node(): sum(0), rems(0) {} Node(int v) { if (v >= 0) sum = v, rems = 0; else sum = 0, rems = 1; } Node(const Node &lnode, const Node &rnode) { int delta = min(lnode.rems, rnode.sum); rems = rnode.rems + lnode.rems - delta; sum = lnode.sum + rnode.sum - delta; } }; template <int N, class AddableNode> class SegmentTree { private: int n; AddableNode st[4 * N]; inline void push_up(int id) { st[id] = AddableNode(st[id << 1], st[id << 1 | 1]); } void update(int id, int l, int r, int i, int v) { if (r < i or i < l) return; if (l == r) { // cerr << "update " << i << ", v = " << v << endl; st[id] = Node(v); return; } int m = (l + r) >> 1; update(id << 1, l, m, i, v); update(id << 1 | 1, m + 1, r, i, v); push_up(id); } AddableNode get(int id, int l, int r, int left, int right) { if (r < left or right < l or right < left or r < l) return AddableNode(); if (left <= l and r <= right) return st[id]; int m = (l + r) >> 1; return AddableNode( get(id << 1, l, m, left, right), get(id << 1 | 1, m + 1, r, left, right) ); } public: inline void init(int _n) { n = _n; } inline void update(int i, int v) { update(1, 1, n, i, v); } inline AddableNode get(int left, int right) { return get(1, 1, n, left, right); } }; const int MAX = 5e5 + 7; int N, Q; char str[MAX]; vector<pair<int, int>> queries_by_l[MAX]; void input() { cin >> N >> (str + 1); cin >> Q; for (int q = 0; q < Q; q++) { int l, r; cin >> l >> r; queries_by_l[l].emplace_back(r, q); } } SegmentTree<MAX, Node> st; void init() { st.init(N); } int ans[MAX]; void solve() { deque<int> de; for (int l = N; l >= 1; l--) { if (str[l] == 'T') { de.push_front(l); } else { // str[l] == 'C' if (not de.empty()) { int j = de.front(); de.pop_front(); // Add matched T st.update(j, -1); } // Add C st.update(l, +1); } for (const auto &query : queries_by_l[l]) { int r, q; tie(r, q) = query; int cnt_T_in_deque = distance( de.begin(), upper_bound(de.begin(), de.end(), r) ); int cnt_T_in_left_seq = st.get(l, r).rems; // cerr << "[l, r] = [" << l << ", " << r << "]" << endl; // cerr << "cnt_T_in_deque = " << cnt_T_in_deque << endl; // cerr << "cnt_T_in_left_seq = " << cnt_T_in_left_seq << endl; ans[q] = cnt_T_in_deque + cnt_T_in_left_seq; } } for (int q = 0; q < Q; q++) cout << ans[q] << '\n'; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); input(); init(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...