Submission #855863

#	Time	Username	Problem	Language	Result	Execution time	Memory
855863		NeroZein	Election (BOI18_election)	C++17	100 / 100	521 ms	49000 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, min_pref, 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); 
    ret.min_pref = min(lc.min_pref, lc.sum + rc.min_pref); 
    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); 
      seg[nd].min_pref = 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 get(int nd, int l, int r, node cur) {
    if (l == r) {
      return l; 
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    node nx = merge(cur, seg[nd + 1]); 
    if (nx.min_pref < 0) {
      return get(nd + 1, l, mid, cur); 
    } 
    return get(rs, mid + 1, r, nx);
  }
  int get() {
    node emp;
    emp.zeros = emp.sum = emp.min_pref = emp.min_suf = 0;
    return seg[0].min_pref >= 0 ? -1 : get(0, 0, n - 1, emp); 
  }
};

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); 
  }
  SegmentTree st(n); 
  for (int i = 0, s = 0; i < n; ++i) {
    if (s + a[i] < 0) {
      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); 
    }
    st.upd(i, 0); 
    if (a[i] == 1) {
      int id = st.get(); 
      //deb(i) deb(id) cout << '\n';
      if (id != -1) {
        st.upd(id, 0); 
      }
    } 
  }
  for (int i = 0; i < q; ++i) {
    cout << ans[i] << '\n'; 
  }
  return 0;
}

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