Submission #1276426

#TimeUsernameProblemLanguageResultExecution timeMemory
1276426minggaElection (BOI18_election)C++20
100 / 100
409 ms36648 KiB
// Author: caption_mingle #include "bits/stdc++.h" using namespace std; #define ln "\n" #define pb push_back #define fi first #define se second #define all(x) (x).begin(), (x).end() #define sz(x) ((int)(x).size()) #define ll long long const int mod = 1e9 + 7; const int inf = 2e9; const int N = 5e5 + 7; int n, q; int a[N]; struct Node { int lef, rig, tot, ans; Node() { lef = rig = tot = ans = 0; } Node(int x) { tot = x; lef = rig = ans = max(0, x); } Node operator + (const Node& o) { Node tmp; tmp.lef = max(lef, tot + o.lef); tmp.rig = max(o.rig, rig + o.tot); tmp.tot = tot + o.tot; tmp.ans = max({lef + o.rig, ans + o.tot, tot + o.ans}); return tmp; } } st[N * 4 + 4]; void build(int i = 1, int l = 1, int r = n) { if(l == r) { st[i] = Node(a[l]); return; } int m = (l + r) >> 1; build(i * 2, l, m); build(i * 2 + 1, m + 1, r); st[i] = st[i * 2] + st[i * 2 + 1]; } Node get(int i, int l, int r, int u, int v) { if(l > v or r < u) return Node(); if(u <= l and r <= v) return st[i]; int m = (l + r) >> 1; return get(i * 2, l, m, u, v) + get(i * 2 + 1, m + 1, r, u, v); } signed main() { cin.tie(0) -> sync_with_stdio(0); #define task "" if(fopen(task ".INP", "r")) { freopen(task ".INP", "r", stdin); freopen(task ".OUT", "w", stdout); } cin >> n; for(int i = 1; i <= n; i++) { char c; cin >> c; if(c == 'T') a[i] = 1; else a[i] = -1; } cin >> q; build(); for(int i = 1; i <= q; i++) { int l, r; cin >> l >> r; cout << get(1, 1, n, l, r).ans << ln; } cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC; }

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:60:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:61:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...