Submission #533650

#	Time	Username	Problem	Language	Result	Execution time	Memory
533650		nemethm	Election (BOI18_election)	C++17	0 / 100	3 ms	332 KiB

election

#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<int> v;

struct Node
{
  int sol, surplus;
};


vector<Node> segtree;
ll mod;

Node unite(Node a, Node b){
  Node ret;
  ret.sol = a.sol + b.sol;
  ret.sol = max({ret.sol - a.surplus, ret.sol - b.surplus, 0});
  ret.surplus = a.surplus + b.surplus - (a.sol + b.sol - ret.sol);
  /*ret.surplus = a.surplus + b.surplus;
  int prev = ret.sol;
  ret.sol = max(ret.sol - ret.surplus, 0);
  ret.surplus -= prev - ret.sol;*/
  return ret;
}

void build(int l, int r, int pos = 1){
  if(l == r){
    segtree[pos] = {!v[l],v[l]};
    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){
      char c;
      cin >> c;
      v[i] = c == 'C' ? 1 : 0; 
    }
    build(1, n);
    cin >> m;
    while(m--){
      ll l, r;
      cin >> l >> r;
      cout << query(l,r, 1, n).sol << endl;
    }
    return 0;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18