Submission #533657

#	Time	Username	Problem	Language	Result	Execution time	Memory
533657		nemethm	Election (BOI18_election)	C++17	0 / 100	4 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<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 = a.lcost + max(b.lcost - a.lsurplus, 0);
  ret.lsurplus = max(a.lsurplus - b.lcost, 0) + b.lsurplus;
  ret.rcost = b.rcost + max(a.rcost - b.rsurplus, 0);
  ret.rsurplus = max(b.rsurplus - a.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);
      //cerr << ans.lcost << " " << ans.lsurplus << " " << ans.rcost << " " << ans.rsurplus << endl;
      cout << max(ans.lcost, ans.rcost) << endl;
    }
    return 0;
}

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