Submission #486944

#	Time	Username	Problem	Language	Result	Execution time	Memory
486944		Victor	Election (BOI18_election)	C++17	100 / 100	1348 ms	58444 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

string str;

struct Node {
    Node *l, *r;
    int lo, hi, sum, best, pref, suf;
    Node(int L, int R) : lo(L), hi(R) {
        if (hi - lo == 1) {
            sum = str[lo] == 'C' ? -1 : 1;
            best = pref = suf = max(sum, 0);

        } else {
            int mid = (lo + hi) / 2;
            l = new Node(lo, mid);
            r = new Node(mid, hi);

            best = max(max(l->best + r->sum, l->sum + r->best), l->pref + r->suf);
            sum = l->sum + r->sum;
            pref = max(l->pref, l->sum + r->pref);
            suf = max(r->suf, r->sum + l->suf);
        }
    }

    pair<ii, ii> query(int L, int R) {
        if (hi <= L || R <= lo) return {{0, 0}, {0, 0}};
        if (L <= lo && hi <= R) return {{sum, best}, {pref, suf}};

        int lsum, lbest, lpref, lsuf;
        auto val = l->query(L, R);
        tie(lsum, lbest) = val.first;
        tie(lpref, lsuf) = val.second;

        int rsum, rbest, rpref, rsuf;
        val = r->query(L, R);
        tie(rsum, rbest) = val.first;
        tie(rpref, rsuf) = val.second;

        int cur_best = max(max(lbest + rsum, lsum + rbest), lpref + rsuf);
        int cur_sum = lsum + rsum;
        int cur_pref = max(lpref, lsum + rpref);
        int cur_suf = max(rsuf, rsum + lsuf);

        return {{cur_sum, cur_best}, {cur_pref, cur_suf}};
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n, q;
    cin >> n >> str >> q;

    Node segtree(0, n);

    while (q--) {
        int lo, hi;
        cin >> lo >> hi;

        auto val = segtree.query(lo - 1, hi);
        int best = val.first.second, pref, suf;
        tie(pref, suf) = val.second;

        cout << max(best,max(pref,suf)) << endl;
    }
    return 0;
}

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