Submission #294222

#	Time	Username	Problem	Language	Result	Execution time	Memory
294222		6aren	Election (BOI18_election)	C++14	100 / 100	1099 ms	33100 KiB

election

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define pb push_back
#define ii pair<int, int>
#define x first
#define y second
#define bit(x, y) ((x >> y) & 1)

const int N = 500005;

int it[4 * N], lazy[4 * N];
int pref[N], suff[N], n, q;

void build(int k, int l, int r) {
    if (l == r) {
        it[k] = suff[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * k, l, mid);
    build(2 * k + 1, mid + 1, r);
    it[k] = min(it[2 * k], it[2 * k + 1]);
}

void down(int k) {
    int val = lazy[k];
    if (val == 0) return;
    it[2 * k] += val;
    it[2 * k + 1] += val;
    lazy[2 * k] += val;
    lazy[2 * k + 1] += val;
    lazy[k] = 0;
    return;
}

void update(int k, int l, int r, int u, int v, int val) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
        it[k] += val;
        lazy[k] += val;
        return;
    }
    down(k);
    int mid = (l + r) / 2;
    update(2 * k, l, mid, u, v, val);
    update(2 * k + 1, mid + 1, r, u, v, val);
    it[k] = min(it[2 * k], it[2 * k + 1]);
}

int get(int k, int l, int r, int u, int v) {
    if (l > v || r < u) return 1e9;
    if (l >= u && r <= v) return it[k];
    down(k);
    int mid = (l + r) / 2;
    int g1 = get(2 * k, l, mid, u, v);
    int g2 = get(2 * k + 1, mid + 1, r, u, v);
    return min(g1, g2);
}

vector<int> eli_id;

void add(int id) {
    while (pref[eli_id.back()] >= pref[id]) {
        update(1, 1, n, 1, eli_id.back(), -1);
        eli_id.pop_back();
    }
    update(1, 1, n, 1, id, 1);
    eli_id.pb(id);
}


int main() {
    ios::sync_with_stdio(false); cin.tie(0); 
    cout.tie(0);
    cin >> n;
    string s;
    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;
    }
    for (int i = n; i > 0; i--) {
        if (s[i] == 'C') suff[i] = suff[i + 1] + 1;
        else suff[i] = suff[i + 1] - 1;
    }
    pref[n + 1] = -1e9;
    eli_id.pb(n + 1);

    build(1, 1, n);
    
    cin >> q;
    vector<pair<ii, int>> que;
    vector<int> ans(q);
    for (int i = 0; i < q; i++) {
        ii u;
        cin >> u.x >> u.y;
        que.pb({u, i});
    }
    sort(que.rbegin(), que.rend());

    int cur = n + 1;
    for (auto qu : que) {
        int l = qu.x.x;
        int r = qu.x.y;
        int id = qu.y;
        while (cur >= l) {
            cur--;
            add(cur);
        }
        // cout << cur << endl;
        // for (int e : eli_id) cout << e << ' ';
        // cout << endl;
        // get the number of id <= r
        ans[id] = eli_id.end() - lower_bound(eli_id.begin(), eli_id.end(), r, greater<int>()) - 1;
        // cout << ans[id] << endl;
        int pivot = suff[r + 1];
        if (r != n) pivot = get(1, 1, n, r + 1, r + 1);

        ans[id] += max(0, pivot - get(1, 1, n, l, r));
    }
    
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
    return 0;
}

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