oj.uz

Submission #571986

# Submission time Handle Problem Language Result Execution time Memory
571986 2022-06-03T08:38:32 Z Shin Election (BOI18_election) C++14
100 / 100
 565 ms 46464 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

struct segment_tree {
  struct Node {
    int sum, ans;
    Node(int _sum = 0, int _ans = 0) {
      sum = _sum;
      ans = _ans;
    }
    Node operator + (const Node &oth) const {
      return Node(sum + oth.sum, min(oth.ans, ans + oth.sum));
    }
  };

  vector<Node> t;
  int n;
  segment_tree(int _n) : n(_n) {
    t.resize((n << 2) + 7);
  }

  void modify(int node, int l, int r, int p, int v) {
    if (l > p || r < p) {
      return;
    }
    if (l == r) {
      t[node] = Node(v, v);
    } else {
      int mid = (l + r) >> 1;
      modify(node << 1, l, mid, p, v);
      modify(node << 1|1, mid + 1, r, p, v);
      t[node] = t[node << 1] + t[node << 1|1];
    }
  }

  Node get(int node, int l, int r, int u, int v) {
    if (l > v || r < u) {
      return Node(0, 0);
    }
    if (u <= l && r <= v) {
      return t[node];
    }
    int mid = (l + r) >> 1;
    Node L = get(node << 1, l, mid, u, v);
    Node R = get(node << 1|1, mid + 1, r, u, v);
    return L + R;
  }

  void modify(int p, int v) {
    modify(1, 1, n, p, v);
  }

  int get(int l, int r) {
    return -get(1, 1, n, l, r).ans;
  }
};

const int N = 5e5 + 7;

int n;
int a[N];
int res[N];
string s;

vector<pair<int, int>> pos[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> s;
  for (int i = 1; i <= n; i ++) {
    a[i] = (s[i - 1]  == 'C' ? 1 : -1);
  }
  int q; cin >> q;
  for (int i = 1; i <= q; i ++) {
    int l, r; cin >> l >> r;
    pos[l].emplace_back(r, i);
  }
  vector<int> s;
  segment_tree st(n);
  for (int l = n; l > 0; l --) {
    if (a[l] == 1) {
      if (!s.empty()) {
        st.modify(-s.back(), -1);
        s.pop_back();
      }
      st.modify(l, 1);
    } else {
      s.push_back(-l);
    }
    for (pair<int, int> x: pos[l]) {
      int r, i; tie(r, i) = x;
      int add = lower_bound(all(s), - r) - s.begin();
      add = (int) s.size() - add;
      res[i] = max(0, st.get(l, r)) + add;
    }
  }
  for (int i = 1; i <= q; i ++) {
    cout << res[i] << '\n';
  }
  return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 8 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 7 ms 12136 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 8 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 7 ms 12136 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 68 ms 16712 KB Output is correct
7 Correct 51 ms 16176 KB Output is correct
8 Correct 50 ms 16140 KB Output is correct
9 Correct 53 ms 16504 KB Output is correct
10 Correct 61 ms 16488 KB Output is correct
11 Correct 82 ms 16696 KB Output is correct
12 Correct 60 ms 16716 KB Output is correct
13 Correct 57 ms 16924 KB Output is correct
14 Correct 56 ms 16656 KB Output is correct
15 Correct 54 ms 16588 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 8 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 7 ms 12136 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 68 ms 16712 KB Output is correct
7 Correct 51 ms 16176 KB Output is correct
8 Correct 50 ms 16140 KB Output is correct
9 Correct 53 ms 16504 KB Output is correct
10 Correct 61 ms 16488 KB Output is correct
11 Correct 82 ms 16696 KB Output is correct
12 Correct 60 ms 16716 KB Output is correct
13 Correct 57 ms 16924 KB Output is correct
14 Correct 56 ms 16656 KB Output is correct
15 Correct 54 ms 16588 KB Output is correct
16 Correct 561 ms 44636 KB Output is correct
17 Correct 436 ms 41060 KB Output is correct
18 Correct 411 ms 41868 KB Output is correct
19 Correct 466 ms 43576 KB Output is correct
20 Correct 523 ms 43728 KB Output is correct
21 Correct 528 ms 46200 KB Output is correct
22 Correct 565 ms 45616 KB Output is correct
23 Correct 561 ms 46464 KB Output is correct
24 Correct 524 ms 45736 KB Output is correct
25 Correct 490 ms 44892 KB Output is correct