oj.uz

Submission #1093112

# Submission time Handle Problem Language Result Execution time Memory
1093112 2024-09-26T01:15:12 Z juicy Election (BOI18_election) C++17
100 / 100
 406 ms 44804 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 5e5 + 5;
 
int n, q;
int res[N];
array<int, 2> tr[4 * N];
string s;
vector<array<int, 2>> que[N];
 
array<int, 2> operator + (const array<int, 2> &lt, const array<int, 2> &rt) {
  return {min(rt[0], lt[0] + rt[1]), lt[1] + rt[1]};
}
 
void upd(int i, int x, int id = 1, int l = 1, int r = n) {
  if (l == r) {
    tr[id] = {x, x};
    return;
  }
  int m = (l + r) / 2;
  if (i <= m) {
    upd(i, x, id * 2, l, m);
  } else {
    upd(i, x, id * 2 + 1, m + 1, r);
  }
  tr[id] = tr[id * 2] + tr[id * 2 + 1];
}
 
array<int, 2> qry(int u, int v, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    return tr[id];
  }
  int m = (l + r) / 2;
  if (v <= m) {
    return qry(u, v, id * 2, l, m);
  }
  if (m < u) {
    return qry(u, v, id * 2 + 1, m + 1, r);
  }
  return qry(u, v, id * 2, l, m) + qry(u, v, id * 2 + 1, m + 1, r);
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> n >> s >> q;
  for (int i = 1; i <= q; ++i) {
    int l, r; cin >> l >> r;
    que[l].push_back({r, i});
  }  
  vector<int> st;
  for (int i = n; i; --i) {
    if (s[i - 1] == 'T') {
      st.push_back(i);
    } else {
      upd(i, 1);
      if (st.size()) {
        upd(st.back(), -1);
        st.pop_back();
      }
    }
    for (auto [j, id] : que[i]) {
      int l = 0, r = int(st.size()) - 1, k = 0;
      while (l <= r) {
        int m = (l + r) / 2;
        if (st[m] <= j) {
          k = st.size() - m;
          r = m - 1;
        } else {
          l = m + 1;
        }
      }
      res[id] = k + max(0, -qry(i, j)[0]);
    }
  }
  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 12124 KB Output is correct
2 Correct 6 ms 12124 KB Output is correct
3 Correct 6 ms 12124 KB Output is correct
4 Correct 8 ms 12376 KB Output is correct
5 Correct 6 ms 12124 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12124 KB Output is correct
2 Correct 6 ms 12124 KB Output is correct
3 Correct 6 ms 12124 KB Output is correct
4 Correct 8 ms 12376 KB Output is correct
5 Correct 6 ms 12124 KB Output is correct
6 Correct 46 ms 17188 KB Output is correct
7 Correct 41 ms 16720 KB Output is correct
8 Correct 41 ms 16728 KB Output is correct
9 Correct 42 ms 16916 KB Output is correct
10 Correct 45 ms 16936 KB Output is correct
11 Correct 51 ms 17236 KB Output is correct
12 Correct 47 ms 17252 KB Output is correct
13 Correct 46 ms 17128 KB Output is correct
14 Correct 46 ms 17072 KB Output is correct
15 Correct 43 ms 17236 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12124 KB Output is correct
2 Correct 6 ms 12124 KB Output is correct
3 Correct 6 ms 12124 KB Output is correct
4 Correct 8 ms 12376 KB Output is correct
5 Correct 6 ms 12124 KB Output is correct
6 Correct 46 ms 17188 KB Output is correct
7 Correct 41 ms 16720 KB Output is correct
8 Correct 41 ms 16728 KB Output is correct
9 Correct 42 ms 16916 KB Output is correct
10 Correct 45 ms 16936 KB Output is correct
11 Correct 51 ms 17236 KB Output is correct
12 Correct 47 ms 17252 KB Output is correct
13 Correct 46 ms 17128 KB Output is correct
14 Correct 46 ms 17072 KB Output is correct
15 Correct 43 ms 17236 KB Output is correct
16 Correct 372 ms 42976 KB Output is correct
17 Correct 293 ms 38884 KB Output is correct
18 Correct 312 ms 40160 KB Output is correct
19 Correct 307 ms 41820 KB Output is correct
20 Correct 355 ms 41960 KB Output is correct
21 Correct 406 ms 44804 KB Output is correct
22 Correct 370 ms 44004 KB Output is correct
23 Correct 390 ms 42972 KB Output is correct
24 Correct 367 ms 43492 KB Output is correct
25 Correct 357 ms 43236 KB Output is correct