Submission #1268350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268350		aeg	Election (BOI18_election)	C++20	100 / 100	441 ms	57360 KiB

election

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

#define int int64_t

struct query {
  int l, r, id;
  query(int l, int r, int id) : l(l), r(r), id(id) {}
};

bool operator<(query const &a, query const &b) { return a.l > b.l; }

struct segtr {
  struct node {
    int tot, suf;
    node(int tot = 0, int suf = 0) : tot(tot), suf(suf) {}
  };

  vector<node> tree;

  node merge(node a, node b) {
    // if (a.suf == INT32_MAX)
    //   return b;
    // else if (b.suf == INT32_MAX)
    //   return a;
    return node(a.tot + b.tot, min(a.suf + b.tot, b.suf));
  }

  void build(int ind, int l, int r, vector<int> const &a) {
    if (l == r) {
      tree[ind].tot = a[l];
      tree[ind].suf = min(int(0), a[l]);
      return;
    }
    int m = (l + r) >> 1;
    build(ind << 1, l, m, a);
    build(ind << 1 | 1, m + 1, r, a);
    tree[ind] = merge(tree[ind << 1], tree[ind << 1 | 1]);
  }
  segtr(vector<int> const &a) : tree(a.size() << 2) {
    build(1, 0, a.size() - 1, a);
  }

  node query(int ind, int l, int r, int tl, int tr) {
    if (tl <= l && tr >= r)
      return tree[ind];

    if (tl > r || tr < l)
      return {0, 0};
    int m = (l + r) >> 1;
    node a = query(ind << 1, l, m, tl, tr),
         b = query(ind << 1 | 1, m + 1, r, tl, tr);
    return merge(a, b);
  }

  void update(int ind, int l, int r, int i, int val) {
    if (i > r || i < l)
      return;
    if (l == r) {
      tree[ind].tot = val;
      tree[ind].suf = min(val, int(0));
      return;
    }
    int m = (l + r) >> 1;
    update(ind << 1, l, m, i, val);
    update(ind << 1 | 1, m + 1, r, i, val);
    tree[ind] = merge(tree[ind << 1], tree[ind << 1 | 1]);
  }
};

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    char c;
    cin >> c;
    if (c == 'C')
      a[i] = 1;
    else
      a[i] = -1;
  }

  int q;
  cin >> q;
  vector<query> quer;
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    quer.emplace_back(l, r, i);
  }
  vector<int> anses(q, 0);
  sort(quer.begin(), quer.end());

  segtr tr(a);

  vector<int> st;
  int curind = n;
  for (int i = 0; i < q; i++) {
    while (curind > quer[i].l) {
      curind--;
      if (a[curind] == 1) {
        if (!st.empty()) {
          tr.update(1, 0, n - 1, st.back(), -1);
          st.pop_back();
        }
      } else {
        tr.update(1, 0, n - 1, curind, 0);
        st.push_back(curind);
      }
    }

    int ans = upper_bound(st.rbegin(), st.rend(), quer[i].r) - st.rbegin();
    ans += -tr.query(1, 0, n - 1, quer[i].l, quer[i].r).suf;
    anses[quer[i].id] = ans;
  }
  copy(anses.begin(), anses.end(), ostream_iterator<int>(cout, "\n"));
}

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