Submission #1264904

#TimeUsernameProblemLanguageResultExecution timeMemory
1264904SDAdzs1tgElection (BOI18_election)C++20
0 / 100
9 ms12352 KiB
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn = 5e5 + 5; int pre[maxn], st[maxn * 4], suff[maxn]; int mn[maxn * 4], ans[maxn]; struct p{ int r, id; }; void build(int id, int l, int r) { if(l == r) { mn[id] = suff[l]; return; } int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); mn[id] = min(mn[id * 2], mn[id * 2 + 1]); } int getmin(int id, int l, int r, int u, int v) { if(r < u || v < l) return 1e18; if(u <= l && r <= v) return mn[id]; int mid = (l + r) / 2; return min(getmin(id * 2, l, mid, u, v), getmin(id * 2 + 1, mid + 1, r, u, v)); } void update(int id, int l, int r, int u, int v) { if(l == r && l == u) { st[id] += v; return; } int mid = (l + r) / 2; if(u > mid) { update(id * 2 + 1, mid + 1, r, u, v); } else update(id * 2, l, mid, u, v); st[id] = st[id * 2] + st[id * 2 + 1]; } int get(int id, int l, int r, int u, int v) { if(r < u || v < l) return 0; if(u <= l && r <= v) return st[id]; int mid = (l + r) / 2; return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); } vector<p> q[maxn]; bool cmp(p a, p b) { return a.r < b.r; } signed main () { int n; cin >> n; string s; cin >> s; s = ' ' + s; for(int i = 1; i <= n; i++) { pre[i] = pre[i - 1]; if(s[i] == 'C') pre[i]++; else pre[i]--; } int t; cin >> t; for(int i = 1; i <= t; i++){ int l, r; cin >> l >> r; q[l].push_back({r, i}); } for(int i = 1; i <= n; i++) { sort(q[i].begin(), q[i].end(), cmp); } stack<int> stk; for(int i = n; i >= 1; i--) { while(!stk.empty() && pre[stk.top()] >= pre[i]) stk.pop(); if(!stk.empty() && pre[stk.top()] < 0) { update(1, 1, n, stk.top(), 1); } stk.push(i); } for(int i = 1; i <= n; i++) { if(get(1, 1, n, i, i)) { s[i] = '0'; } } for(int i = n; i >= 1; i--) { suff[i] = suff[i + 1]; if(s[i] == 'C') suff[i]++; else if(s[i] == 'T') suff[i]--; } build(1, 1, n); for(int l = 1; l <= n; l++) { for(auto r : q[l]) { ans[r.id] = get(1, 1, n, l, r.r) + suff[r.r + 1] - getmin(1, 1, n, l, r.r); ans[r.id] = max(ans[r.id], 0ll); } } for(int i = 1; i <= t; i++) { cout << ans[i] << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...