oj.uz

Submission #1091705

# Submission time Handle Problem Language Result Execution time Memory
1091705 2024-09-21T20:34:02 Z LucaLucaM Election (BOI18_election) C++17
100 / 100
 330 ms 37012 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#warning That's not the baby, that's my baby

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

const int INF = 1e9;
const int NMAX = 5e5;

int pref[NMAX + 1];

struct Node {
  int mini, maxi, answer;
  Node() : mini(INF), maxi(-INF), answer(0) {}
  Node operator + (const Node &other) const {
    Node ret;
    ret.answer = std::min(std::min(answer, other.answer), mini - other.maxi);
    ret.answer = std::min(ret.answer, 0);
    ret.mini = std::min(mini, other.mini);
    ret.maxi = std::max(maxi, other.maxi);
    return ret;
  };
};

Node aint[4 * NMAX + 1];

void build(int node, int tl, int tr) {
  if (tl == tr) {
    aint[node].mini = aint[node].maxi = pref[tl];
    aint[node].answer = INF;
  } else {
    int mid = (tl + tr) / 2;
    build(2 * node, tl, mid);
    build(2 * node + 1, mid + 1, tr);
    aint[node] = aint[2 * node] + aint[2 * node + 1];
  }
}
Node query(int node, int tl, int tr, int l, int r) {
  if (l <= tl && tr <= r) {
    return aint[node];
  }
  int mid = (tl + tr) / 2;
  if (l <= mid && mid < r) {
    return query(2 * node, tl, mid, l, r) + query(2 * node + 1, mid + 1, tr, l, r);
  } else if (l <= mid) {
    return query(2 * node, tl, mid, l, r);
  } else {
    return query(2 * node + 1, mid + 1, tr, l, r);
  }
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif

  int n;
  std::cin >> n;
  
  std::string s;
  std::cin >> s;
  s = '$' + s;

  for (int i = 1; i <= n; i++) {
    if (s[i] == 'C') {
      pref[i] = pref[i - 1] + 1;
    } else {
      pref[i] = pref[i - 1] - 1;
    }
  }

  build(1, 0, n);

  int q;
  std::cin >> q;
  while (q--) {
    int l, r;
    std::cin >> l >> r;
    std::cout << pref[l - 1] - query(1, 0, n, l - 1, r).answer - pref[r] << '\n';    
  }

  return 0;
}

Compilation message

election.cpp:5:2: warning: #warning That's not the baby, that's my baby [-Wcpp]
    5 | #warning That's not the baby, that's my baby
      |  ^~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23900 KB Output is correct
2 Correct 9 ms 23900 KB Output is correct
3 Correct 9 ms 23988 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 9 ms 23900 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23900 KB Output is correct
2 Correct 9 ms 23900 KB Output is correct
3 Correct 9 ms 23988 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 9 ms 23900 KB Output is correct
6 Correct 41 ms 25420 KB Output is correct
7 Correct 41 ms 25424 KB Output is correct
8 Correct 41 ms 25424 KB Output is correct
9 Correct 34 ms 25420 KB Output is correct
10 Correct 40 ms 25424 KB Output is correct
11 Correct 41 ms 25516 KB Output is correct
12 Correct 49 ms 25424 KB Output is correct
13 Correct 47 ms 25628 KB Output is correct
14 Correct 42 ms 25420 KB Output is correct
15 Correct 41 ms 25420 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23900 KB Output is correct
2 Correct 9 ms 23900 KB Output is correct
3 Correct 9 ms 23988 KB Output is correct
4 Correct 9 ms 23896 KB Output is correct
5 Correct 9 ms 23900 KB Output is correct
6 Correct 41 ms 25420 KB Output is correct
7 Correct 41 ms 25424 KB Output is correct
8 Correct 41 ms 25424 KB Output is correct
9 Correct 34 ms 25420 KB Output is correct
10 Correct 40 ms 25424 KB Output is correct
11 Correct 41 ms 25516 KB Output is correct
12 Correct 49 ms 25424 KB Output is correct
13 Correct 47 ms 25628 KB Output is correct
14 Correct 42 ms 25420 KB Output is correct
15 Correct 41 ms 25420 KB Output is correct
16 Correct 330 ms 36212 KB Output is correct
17 Correct 294 ms 35572 KB Output is correct
18 Correct 308 ms 36028 KB Output is correct
19 Correct 222 ms 35320 KB Output is correct
20 Correct 309 ms 35112 KB Output is correct
21 Correct 312 ms 36856 KB Output is correct
22 Correct 317 ms 36720 KB Output is correct
23 Correct 303 ms 37012 KB Output is correct
24 Correct 289 ms 36604 KB Output is correct
25 Correct 295 ms 36212 KB Output is correct