Submission #855860

#	Time	Username	Problem	Language	Result	Execution time	Memory
855860		NeroZein	Election (BOI18_election)	C++17	0 / 100	2 ms	600 KiB

election

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

struct SegmentTree {
  struct node {
    int sum, min_suf, zeros; 
  };
  int n; 
  vector<node> seg;
  SegmentTree (int n_) : n(n_) {
    seg.resize(2 * n - 1); 
  }
  node merge(const node& lc, const node& rc) {
    node ret;
    ret.sum = lc.sum + rc.sum;
    ret.zeros = lc.zeros + rc.zeros; 
    ret.min_suf = min(rc.min_suf, rc.sum + lc.min_suf); 
    return ret;
  }
  void upd(int nd, int l, int r, int p, int v) {
    if (l == r) {
      seg[nd].sum = v; 
      seg[nd].zeros = v == 0;
      seg[nd].min_suf = min(0, v); 
      return;
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (p <= mid) {
      upd(nd + 1, l, mid, p, v); 
    } else {
      upd(rs, mid + 1, r, p, v); 
    }
    seg[nd] = merge(seg[nd + 1], seg[rs]); 
  }
  void upd(int p, int v) {
    upd(0, 0, n - 1, p, v); 
  }
  node qry(int nd, int l, int r, int s, int e) {
    if (l >= s && r <= e) {
      return seg[nd];
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (mid >= e) {
      return qry(nd + 1, l, mid, s, e);
    } else {
      if (mid < s) {
        return qry(rs, mid + 1, r, s, e); 
      } else {
        return merge(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e)); 
      }
    }
  }
  int qry(int l, int r) {
    node ret = qry(0, 0, n - 1, l, r); 
    return ret.min_suf - ret.zeros;
  }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n); 
  for (int i = 0; i < n; ++i) {
    char c;
    cin >> c;
    a[i] = (c == 'C' ? 1 : -1); 
  }
  set<int> se; 
  vector<int> nullified(n); 
  SegmentTree st(n); 
  for (int i = 0, s = 0; i < n; ++i) {
    if (s + a[i] < 0) {
      nullified[i] = 1; 
      se.insert(i); 
      st.upd(i, 0); 
    }
    else {
      s += a[i]; 
      st.upd(i, a[i]); 
    }
  }
  int q;
  cin >> q;
  vector<vector<pair<int, int>>> qs(n); 
  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    qs[l].emplace_back(r, i); 
  }
  vector<int> ans(q); 
  for (int i = 0; i < n; ++i) {
    for (auto [qr, qi] : qs[i]) {
      ans[qi] = -st.qry(i, qr); 
    }
    if (a[i] == 1) {
      auto f = se.lower_bound(i); 
      if (f != se.end()) {
        se.insert(*f - 1); 
        nullified[*f - 1] = 1; 
        st.upd(*f - 1, 0); 
      } 
    } else if (nullified[i]) {
      se.erase(i); 
    }
  }
  for (int i = 0; i < q; ++i) {
    cout << ans[i] << '\n'; 
  }
  return 0;
}

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