oj.uz

Submission #855863

# Submission time Handle Problem Language Result Execution time Memory
855863 2023-10-02T04:58:13 Z NeroZein Election (BOI18_election) C++17
100 / 100
 521 ms 49000 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 52 ms 6624 KB Output is correct
7 Correct 58 ms 6736 KB Output is correct
8 Correct 49 ms 6748 KB Output is correct
9 Correct 46 ms 7052 KB Output is correct
10 Correct 49 ms 7116 KB Output is correct
11 Correct 50 ms 7252 KB Output is correct
12 Correct 55 ms 7340 KB Output is correct
13 Correct 47 ms 7252 KB Output is correct
14 Correct 47 ms 7328 KB Output is correct
15 Correct 48 ms 7352 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 52 ms 6624 KB Output is correct
7 Correct 58 ms 6736 KB Output is correct
8 Correct 49 ms 6748 KB Output is correct
9 Correct 46 ms 7052 KB Output is correct
10 Correct 49 ms 7116 KB Output is correct
11 Correct 50 ms 7252 KB Output is correct
12 Correct 55 ms 7340 KB Output is correct
13 Correct 47 ms 7252 KB Output is correct
14 Correct 47 ms 7328 KB Output is correct
15 Correct 48 ms 7352 KB Output is correct
16 Correct 521 ms 48160 KB Output is correct
17 Correct 382 ms 44324 KB Output is correct
18 Correct 390 ms 45308 KB Output is correct
19 Correct 400 ms 46816 KB Output is correct
20 Correct 433 ms 47136 KB Output is correct
21 Correct 484 ms 48884 KB Output is correct
22 Correct 445 ms 48980 KB Output is correct
23 Correct 474 ms 49000 KB Output is correct
24 Correct 418 ms 48732 KB Output is correct
25 Correct 426 ms 48244 KB Output is correct