Submission #1091704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091704		LucaLucaM	Election (BOI18_election)	C++17	0 / 100	11 ms	23956 KiB

election

#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);

  for (int i = 0; i <= n; i++) {
    std::cout << pref[i] << ' ';
  }
  std::cout << '\n';
  std::cout << query(1, 0, n, 3, 9).answer << '\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 (stderr)

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: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18