Submission #770491

#TimeUsernameProblemLanguageResultExecution timeMemory
770491allllekssssaElection (BOI18_election)C++14
0 / 100
1 ms340 KiB
#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; const int inf = 1e9; const int sz = 20; const int maxN = 1<<sz; struct node { int lef; int rig; int sum; }; int n, q; string s; int dl[maxN], dr[maxN]; node merge(node nd1, node nd2) { return {max(nd1.lef, nd2.lef), max(nd1.rig, nd2.rig), max(nd1.sum, nd2.sum)}; } node tree[maxN]; void update(node nd, int idx) { while(idx) { tree[idx] = merge(tree[idx], nd); idx/=2; } } node get(int idx, int tl, int tr, int l, int r) { if (tl > r || tr < l) { return {-inf, -inf, -inf}; } if (tl >= l && tr <= r) { return tree[idx]; } int mid = (tl + tr) / 2; node nd1 = get(2 * idx, tl, mid, l, r); node nd2 = get(2 * idx + 1, mid + 1, tr, l, r); return merge(nd1, nd2); } int main() { cin >> n; cin >> s; cin >> q; for (int i = 1; i < sz; i++) { tree[i] = {-inf, -inf, -inf}; } int cur = 0; for (int i = 1; i<=n; i++) { if (s[i - 1] == 'T') ++cur; else --cur; dl[i] = cur; } cur = 0; for (int i = n; i>0; i--) { dr[i] = cur; node nd = {dl[i], dr[i], dl[i] + dr[i]}; update(nd, i + sz/2 - 1); if (s[i - 1] == 'T') ++cur; else --cur; } while(q--) { int l, r; scanf("%d%d", &l, &r); node nd = get(1, 1, sz/2, l, r); int pl = dl[l - 1]; int pr = dr[r]; int ans = max(0, max(nd.lef - pl, max(nd.rig - pr, nd.sum - pl - pr))); printf("%d\n", ans); } }

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d%d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...