Submission #83239

#TimeUsernameProblemLanguageResultExecution timeMemory
83239polyfishElection (BOI18_election)C++14
100 / 100
1326 ms135256 KiB
//Pantyhose(black) + glasses = infinity #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << x << '\n'; #define BP() cerr << "OK!\n"; #define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define FILE_NAME "data" const int INF = 1e9; const int MAX_N = 500002; class segment_tree { public: vector<pair<int, int> > st; int n; segment_tree(int _n) { n = _n; st.resize(4*n, make_pair(0, 0)); } void down(int id) { int tmp = st[id].second; st[id].second = 0; st[id*2].first += tmp; st[id*2].second += tmp; st[id*2+1].first += tmp; st[id*2+1].second += tmp; } void upd(int u, int v, int val, int l, int r, int id) { if (v<l || u>r) return; if (u<=l && r<=v) { st[id].first += val; st[id].second += val; return; } int mid = (l + r) / 2; down(id); upd(u, v, val, l, mid, id*2); upd(u, v, val, mid+1, r, id*2+1); st[id].first = min(st[id*2].first, st[id*2+1].first); } int get(int u, int v, int l, int r, int id) { if (v<l || u>r) return INF; if (u<=l && r<=v) return st[id].first; int mid = (l + r) / 2; down(id); return min(get(u, v, l, mid, id*2), get(u, v, mid+1, r, id*2+1)); } void upd(int u, int v, int val) { upd(u, v, val, 1, n, 1); } int get(int u, int v) { return get(u, v, 1, n, 1); } }; int n, nQueries, a[MAX_N], suff_sum[MAX_N], pref_sum[MAX_N], res[MAX_N]; vector<pair<int, int> > q[MAX_N]; string S; void enter() { cin >> n >> S >> nQueries; S = '@' + S; for (int i=1; i<=nQueries; ++i) { int l, r; cin >> l >> r; q[l].push_back(make_pair(r, i)); } } void init() { } void solve() { segment_tree tr(n); for (int i=1; i<=n; ++i) a[i] = S[i]=='T' ? -1 : 1; for (int i=1; i<=n; ++i) suff_sum[i] = suff_sum[i-1] + a[i]; for (int i=n; i>=1; --i) { pref_sum[i] = pref_sum[i+1] + a[i]; tr.upd(i, i, pref_sum[i]); } vector<int> p; for (int l=n; l>=1; --l) { if (a[l]==-1) { p.push_back(l); tr.upd(1, l, 1); //debug(tr.get(3, 8)); } else { while (p.size() && suff_sum[p.back()] - suff_sum[l-1] >= 0) { tr.upd(1, p.back(), -1); //debug(tr.get(3, 8)); p.pop_back(); } } for (int j=0; j<q[l].size(); ++j) { int r = q[l][j].first; //debug(tr.get(r+1, r+1)); if (r<n) res[q[l][j].second] = max(0, -(tr.get(l, r) - tr.get(r+1, r+1))) + upper_bound(p.rbegin(), p.rend(), r) - p.rbegin(); else res[q[l][j].second] = max(0, -tr.get(l, r)) + upper_bound(p.rbegin(), p.rend(), r) - p.rbegin(); } } for (int i=1; i<=nQueries; ++i) cout << res[i] << '\n'; } int main() { #ifdef GLASSES_GIRL freopen(FILE_NAME".inp", "r", stdin); freopen(FILE_NAME".out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); enter(); solve(); }

Compilation message (stderr)

election.cpp: In function 'void solve()':
election.cpp:109:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<q[l].size(); ++j) {
                       ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...