제출 #580137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
580137		jmokut	Election (BOI18_election)	C++17	100 / 100	509 ms	27996 KiB

election

#include <iostream>
#include <vector>
#include <iomanip>
#include "algorithm"
#include <cmath>
#include <set>
#include <queue>
#include <random>
#include <chrono>
#include "unordered_set"
#include <unordered_map>
#include "map"
#include "numeric"
#include "climits"
#include "bitset"

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define max4(p, q, r, t) max(max(p, q), max(r, t))
#define max3(p, q, r) max(max(p, q), r)
#define testcases int t; cin>>t; while(t--)
using namespace std;

struct node {
    int pref{} ;
    int suff{};
    int sum{};
    int ans{};

    node() = default;

    node(int pref, int suff, int sum, int ans) : pref(pref), suff(suff), sum(sum), ans(ans) {};
};

const int N = 5e5 + 5;
node T[N << 2];
string s;


node pull(node &u, node &v) {
    int pref = max(u.pref, u.sum + v.pref);
    int suff = max(v.suff, v.sum + u.suff);
    int sum = u.sum + v.sum;
    int ans = max(u.pref + v.suff, max(u.ans + v.sum, v.ans + u.sum));
    return {pref, suff, sum, ans};
}

void pull(int v, int tl, int tr) {
    T[v] = pull(T[v << 1], T[v << 1 | 1]);
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        int val = s[tl] == 'C' ? -1 : 1;
        T[v].ans = max(0, val);
        T[v].pref = T[v].ans;
        T[v].suff = T[v].ans;
        T[v].sum = val;
        return;
    }
    int mid = (tl + tr) >> 1;
    build(v << 1, tl, mid);
    build(v << 1 | 1, mid + 1, tr);
    pull(v, tl, tr);
}


node get_ans(int v, int tl, int tr, int l, int r) {
    if (l == tl && r == tr) {
        return T[v];
    }
    int mid = (tl + tr) >> 1;
    if (r <= mid) {
        return get_ans(v << 1, tl, mid, l, r);
    }
    if (l > mid) {
        return get_ans(v << 1 | 1, mid + 1, tr, l, r);
    }
    node left = get_ans(v << 1, tl, mid, l, mid);
    node right = get_ans(v << 1 | 1, mid + 1, tr, mid + 1, r);

    return pull(left, right);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    cin >> s;

    build(1, 0, n - 1);

    int q;
    cin >> q;

    while (q--) {

        int l, r;
        cin >> l >> r;
        --l, --r;

        node ans = get_ans(1, 0, n - 1, l, r);

        cout << ans.ans << '\n';
    }

}

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