Submission #519530

#TimeUsernameProblemLanguageResultExecution timeMemory
519530akhan42Election (BOI18_election)C++17
0 / 100
2 ms440 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define F first #define S second #define forn(i, n) for(int i = 0; i < n; ++i) #define forbn(i, b, n) for(int i = b; i < n; ++i) #define sz(v) (int)v.size() #define pb push_back #define eb emplace_back #define all(v) v.begin(), v.end() typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef long long ll; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; template <class T> inline void mineq(T &a, T b) { a = min(a, b); } template <class T> inline void maxeq(T &a, T b) { a = max(a, b); } const int INF = 1000 * 1000 * 1000; struct Seg { int n; vi add, mn; Seg(int n, vi &vals): n(n) { add.assign(4 * n, 0); mn.assign(4 * n, 0); build(vals); } void propagate(int v, int tl, int tr) { if(tl == tr || add[v] == 0) return; add[2 * v] += add[v]; add[2 * v + 1] += add[v]; mn[2 * v] += add[v]; mn[2 * v + 1] += add[v]; add[v] = 0; } void pull(int v) { mn[v] = min(mn[2 * v], mn[2 * v + 1]); } void build(vi &vals, int v = 1, int tl = 0, int tr = -1) { if(tr == -1) tr = n - 1; if(tl == tr) { mn[v] = vals[tl]; return; } int tm = (tl + tr) / 2; build(vals, 2 * v, tl, tm); build(vals, 2 * v + 1, tm + 1, tr); pull(v); } void update(int l, int r, int val, int v = 1, int tl = 0, int tr = -1) { if(tr == -1) tr = n - 1; propagate(v, tl, tr); if(l > r) return; if(tl == l && r == tr) { add[v] = val; mn[v] += val; return; } int tm = (tl + tr) / 2; update(l, min(r, tm), val, 2 * v, tl, tm); update(max(l, tm + 1), r, val, 2 * v + 1, tm + 1, tr); pull(v); } int query(int l, int r, int v = 1, int tl = 0, int tr = -1) { if(tr == -1) tr = n - 1; propagate(v, tl, tr); if(l > r) return INF; if(tl == l && r == tr) return mn[v]; int tm = (tl + tr) / 2; int ql = query(l, min(r, tm), 2 * v, tl, tm); int qr = query(max(l, tm + 1), r, 2 * v + 1, tm + 1, tr); return min(ql, qr); } }; void solve() { int n, q; string s; cin >> n >> s >> q; vii qs[n]; forn(i, q) { int l, r; cin >> l >> r; l--; r--; qs[r].eb(l, i); } vi pr(n); forn(i, n) { pr[i] = (s[i] == 'C' ? 1 : -1); if(i) pr[i] += pr[i - 1]; } Seg sg_pr(n, pr); ordered_set turned_off; vi ans(q); forn(r, n) { if(s[r] == 'T') { turned_off.insert(r); sg_pr.update(r, n - 1, +1); } else if(sz(turned_off)) { int w = *turned_off.rbegin(); turned_off.erase(w); sg_pr.update(w, n - 1, -1); } for(ii li: qs[r]) { int l = li.F, i = li.S; int mn = sg_pr.query(l, r); int rem = sz(turned_off) - turned_off.order_of_key(l); ans[i] = -min(0, mn) + rem; } } for(int a: ans) cout << a << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr); // freopen("optmilk.in", "r", stdin); // freopen("optmilk.out", "w", stdout); int t = 1; // cin >> t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...