Submission #533656

#TimeUsernameProblemLanguageResultExecution timeMemory
533656nemethmElection (BOI18_election)C++17
0 / 100
4 ms332 KiB
#include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <deque> #include <map> #include <queue> #include <stack> #include <set> using namespace std; using ll = long long int; vector<char> v; struct Node { int lcost, lsurplus, rcost, rsurplus; }; vector<Node> segtree; ll mod; Node unite(Node a, Node b){ //left side a, right side b Node ret; ret.lcost = max(a.lcost + b.lcost - a.lsurplus, 0); ret.lsurplus = max(a.lsurplus - a.lcost - b.lcost, 0) + b.lsurplus; ret.rcost = max(a.rcost + b.rcost - b.rsurplus, 0); ret.rsurplus = max(b.rsurplus - a.lcost - b.lcost, 0) + a.rsurplus; return ret; } void build(int l, int r, int pos = 1){ if(l == r){ if(v[l] == 'C') segtree[pos] = {0,1,0,1}; else{ segtree[pos] = {1, 0,1,0}; } return; } int m = (l + r) / 2; build(l, m, 2 * pos); build(m + 1, r, 2 * pos + 1); segtree[pos] = unite(segtree[2 * pos], segtree[2 * pos + 1]); } Node query(int l, int r, int tl, int tr, int pos = 1){ if(tl == l && tr == r){ return segtree[pos]; } int m = (tl + tr) / 2; if(r <= m){ return query(l,r, tl, m, 2 * pos); } else if(l > m){ return query(l,r, m + 1, tr, 2 * pos + 1); } else{ return unite(query(l,m, tl, m, 2 * pos), query(m + 1,r, m + 1, tr, 2 * pos + 1)); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n; v.resize(n + 5,0); segtree.resize(4 * n + 10); for(int i = 1; i <= n; ++i){ cin >> v[i]; } build(1, n); cin >> m; while(m--){ ll l, r; cin >> l >> r; Node ans= query(l,r, 1, n); cout << max(ans.lcost, ans.rcost) << endl; } return 0; } /*ret.sol = a.sol + b.sol; ret.sol = max({ret.sol - a.surplus, ret.sol - b.surplus, 0}); ret.surplus = min({a.surplus, b.surplus}); /*ret.surplus = a.surplus + b.surplus; int prev = ret.sol; ret.sol = max(ret.sol - ret.surplus, 0); ret.surplus -= prev - ret.sol;*/

Compilation message (stderr)

election.cpp:88:3: warning: "/*" within comment [-Wcomment]
   88 |   /*ret.surplus = a.surplus + b.surplus;
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...