Submission #1268181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268181		Alebn	Election (BOI18_election)	C++20	0 / 100	3 ms	576 KiB

election

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;

// RECURSIVE
struct Seg {
    struct N {
        int mi, ma, spec, sum;
        N(int mii, int mai, int speci, int sumi):mi(mii),ma(mai),spec(speci),sum(sumi){}
        N(){}
    };
    vector<N> seggy;
    Seg(vector<int>& a) {
        seggy = vector<N>(4 * a.size());
        build(a, 1, 0, a.size() - 1);
    }
    N merge(N a, N b) {
        N temp(min(a.mi, b.mi + a.sum), max(a.ma, b.ma + a.sum), max(b.ma + a.sum - a.mi, max(a.spec, b.spec)), a.sum + b.sum);
        return temp;
    }
    N build(vector<int>& a, int i, int l, int r) {
        if(l == r) return seggy[i] = N(min(0LL, a[l]), max(0LL, a[l]), max(0LL, a[l]), a[l]);
        return seggy[i] = merge(build(a, 2 * i, l, (l + r) / 2), build(a, 2 * i + 1, (l + r) / 2 + 1, r));
    }
    N query(int i, int l, int r, int ql, int qr) {
        if(qr < l || r < ql) return N(LONG_MAX, LONG_MIN, 0, 0);
        if(ql <= l && r <= qr) return seggy[i];
        N temp = merge(query(2 * i, l, (l + r) / 2, ql, qr), query(2 * i + 1, (l + r) / 2 + 1, r, ql, qr));
        return temp;
    }
};

signed main() {
    int n, q, x, y;
    string s;
    cin >> n >> s;
    vector<int> a(n), pref(n);
    for(int i = 0; i < n; i++) {
        if(s[i] == 'C') a[i] = 1;
        else a[i] = -1;
        pref[i] = a[i] + (i ? pref[i - 1] : 0);
    }
    function<int(int,int)> sum = [&](int l, int r) {
        return pref[r] - (l ? pref[l - 1] : 0);
    };
    Seg seggy(a);
    Seg::N temp;
    cin >> q;
    while(q--) {
        cin >> x >> y;
        // abs(temp) --> min in [x, y] - pref[x - 1]
        // ma - sum(x, y) --> spec max in [x, y]  - sum(x, y)
        // min in [x, y]     spec max in [x, y]
        temp = seggy.query(1, 0, n - 1, --x, --y);
        cout << max(temp.spec - sum(x, y), abs(temp.mi)) << "\n";
    }
}

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