oj.uz

Submission #294222

# Submission time Handle Problem Language Result Execution time Memory
294222 2020-09-08T17:22:57 Z 6aren Election (BOI18_election) C++14
100 / 100
 1099 ms 33100 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 120 ms 5480 KB Output is correct
7 Correct 137 ms 5480 KB Output is correct
8 Correct 113 ms 5480 KB Output is correct
9 Correct 112 ms 5480 KB Output is correct
10 Correct 120 ms 5380 KB Output is correct
11 Correct 121 ms 5752 KB Output is correct
12 Correct 117 ms 5608 KB Output is correct
13 Correct 115 ms 5864 KB Output is correct
14 Correct 118 ms 5608 KB Output is correct
15 Correct 116 ms 5480 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 120 ms 5480 KB Output is correct
7 Correct 137 ms 5480 KB Output is correct
8 Correct 113 ms 5480 KB Output is correct
9 Correct 112 ms 5480 KB Output is correct
10 Correct 120 ms 5380 KB Output is correct
11 Correct 121 ms 5752 KB Output is correct
12 Correct 117 ms 5608 KB Output is correct
13 Correct 115 ms 5864 KB Output is correct
14 Correct 118 ms 5608 KB Output is correct
15 Correct 116 ms 5480 KB Output is correct
16 Correct 1098 ms 31496 KB Output is correct
17 Correct 982 ms 30984 KB Output is correct
18 Correct 1031 ms 31376 KB Output is correct
19 Correct 944 ms 30924 KB Output is correct
20 Correct 1018 ms 30472 KB Output is correct
21 Correct 1099 ms 32392 KB Output is correct
22 Correct 1065 ms 32268 KB Output is correct
23 Correct 1078 ms 33100 KB Output is correct
24 Correct 1049 ms 32136 KB Output is correct
25 Correct 1051 ms 31500 KB Output is correct