Submission #134256

#TimeUsernameProblemLanguageResultExecution timeMemory
134256mirbek01Election (BOI18_election)C++11
100 / 100
2696 ms53212 KiB
# include <bits/stdc++.h> using namespace std; const int N = 5e5 + 3; struct node{ int sum, mn; node(){ sum = mn = 0; } } t[N * 4]; int n; string s; int q, ans[N]; vector < pair <int, int> > qe[N]; vector <int> st; node _new; node combine(node a, node b){ a.mn = min(b.mn, a.mn + b.sum); a.sum += b.sum; return a; } void build(int v = 1, int tl = 1, int tr = n){ if(tl == tr){ t[v].sum = (s[tl] == 'C'?1:-1); t[v].mn = t[v].sum; } else { int tm = (tl + tr) >> 1; build(v << 1, tl, tm); build(v << 1 | 1, tm + 1, tr); t[v] = combine(t[v << 1], t[v << 1 | 1]); } } void upd(int pos, int val, int v = 1, int tl = 1, int tr = n){ if(tl == tr){ t[v].sum = t[v].mn = val; } else { int tm = (tl + tr) >> 1; if(pos <= tm) upd(pos, val, v << 1, tl, tm); else upd(pos, val, v << 1 | 1, tm + 1, tr); t[v] = combine(t[v << 1], t[v << 1 | 1]); } } node get(int l, int r, int v = 1, int tl = 1, int tr = n){ if(l > tr || tl > r) return _new; if(l <= tl && tr <= r) return t[v]; int tm = (tl + tr) >> 1; return combine(get(l, r, v << 1, tl, tm), get(l, r, v << 1 | 1, tm + 1, tr)); } int main(){ cin >> n >> s >> q; s = ' ' + s; for(int i = 1; i <= q; i ++){ int l, r; cin >> l >> r; qe[l].emplace_back(r, i); } build(); for(int i = n; i >= 1; i --){ if(s[i] == 'T'){ st.push_back(i); upd(i, 0); } else if(!st.empty()){ upd(st.back(), -1); st.pop_back(); } for(int j = 0; j < (int)qe[i].size(); j ++){ int ret = upper_bound(st.rbegin(), st.rend(), qe[i][j].first) - st.rbegin(); ret -= min(get(i, qe[i][j].first).mn, 0); ans[ qe[i][j].second ] = ret; } } for(int i = 1; i <= q; i ++) cout << ans[i] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...