제출 #1290321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290321		LIA	Election (BOI18_election)	C++17	100 / 100	204 ms	56552 KiB

election

//
// Created by liasa on 12/11/2025.
//

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>

struct Node {
  ll l, r, sum, mx_pre, mx_suf, ans;
};

struct Seg {
  vector<Node> seg;
  ll sz = 1;
  const ll inf = 1e18;
  Seg(ll n, vll &arr) {
    for (; sz < n; sz *= 2)
      ;
    seg.resize(2 * sz);
    for (ll i = 0; i < n; ++i) {
      seg[sz + i] = {
          i, i, arr[i], max(0LL, arr[i]), max(0LL, arr[i]), max(0LL, arr[i])};
    }

    for (ll i = sz - 1; i >= 1; --i) {
      seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
    }
  }

  Node merge(Node &a, Node &b) {
    Node ret = {-1, -1, -1, -1, -1, -1};
    ret.l = a.l;
    ret.r = b.r;
    ret.sum = a.sum + b.sum;
    ret.mx_pre = max(a.mx_pre, a.sum + b.mx_pre);
    ret.mx_suf = max(b.mx_suf, b.sum + a.mx_suf);
    ret.ans = max({a.ans + b.sum, a.sum + b.ans, a.mx_pre + b.mx_suf});
    return ret;
  }
  ll query(ll l, ll r) {
    Node L = {0, 0, 0, 0, 0, -inf}, R = {0, 0, 0, 0, 0, -inf};
    l += sz;
    r += sz;
    while (l <= r) {
      if (l & 1)
        L = merge(L, seg[l++]);
      if (!(r & 1))
        R = merge(seg[r--], R);
      l >>= 1;
      r >>= 1;
    }
    return merge(L, R).ans;
  }
};

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  ll n, q;
  cin >> n;
  vll arr(n);
  for (ll i = 0; i < n; ++i) {
    char c;
    cin >> c;
    if (c == 'C') {
      arr[i] = -1;
    } else
      arr[i] = 1;
  }

  Seg seg(n, arr);
  cin >> q;
  while (q--) {
    ll l, r;
    cin >> l >> r;
    l--;
    r--;
    cout << seg.query(l, r) << "\n";
  }
}

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