oj.uz

Submission #90441

# Submission time Handle Problem Language Result Execution time Memory
90441 2018-12-21T16:15:48 Z choikiwon Election (BOI18_election) C++17
100 / 100
 1699 ms 125088 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MN = 500010;

int N, Q;
char S[MN];
vector<pii> query[MN];
int ans[MN];

struct BIT {
    vector<pii> tree;
    vector<int> lazy;
    void init() {
        tree = vector<pii>(4 * N);
        lazy = vector<int>(4 * N, 0);
        build(0, N - 1, 1);
    }
    void build(int l, int r, int n) {
        if(l == r) {
            tree[n] = pii(0, l);
            return;
        }
        int m = (l + r)>>1;
        build(l, m, 2*n);
        build(m + 1, r, 2*n + 1);
        tree[n] = min(tree[2*n], tree[2*n + 1]);
    }
    void prop(int l, int r, int n) {
        if(l != r) {
            tree[2*n].first += lazy[n];
            lazy[2*n] += lazy[n];
            tree[2*n + 1].first += lazy[n];
            lazy[2*n + 1] += lazy[n];
            lazy[n] = 0;
        }
    }
    void upd(int a, int b, int d, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            tree[n].first += d;
            lazy[n] += d;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd(a, b, d, l, m, 2*n);
        upd(a, b, d, m + 1, r, 2*n + 1);
        tree[n] = min(tree[2*n], tree[2*n + 1]);
    }
    pii quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return pii(1e9, 1e9);
        if(a <= l && r <= b) return tree[n];
        prop(l, r, n);
        int m = (l + r)>>1;
        pii L = quer(a, b, l, m, 2*n);
        pii R = quer(a, b, m + 1, r, 2*n + 1);
        return min(L, R);
    }
    int kquer(int k, int l, int r, int n) {
        if(tree[n].first >= k) return -1;
        if(l == r) return l;
        prop(l, r, n);
        int m = (l + r)>>1;
        if(tree[2*n].first < k) return kquer(k, l, m, 2*n);
        else return kquer(k, m + 1, r, 2*n + 1);
    }
} bit1, bit2;

struct Fenwick {
    vector<int> tree;
    void init() {
        tree = vector<int>(N + 1, 0);
    }
    void upd(int idx, int val) {
        for(int i = idx + 1; i <= N; i += (i & -i)) tree[i] += val;
    }
    int quer(int a) {
        int ret = 0;
        for(int i = a + 1; i >= 1; i -= (i & -i)) ret += tree[i];
        return ret;
    }
    int quer(int a, int b) {
        return quer(b) - quer(a - 1);
    }
} fw;

int main() {
    scanf("%d\n", &N);

    for(int i = 0; i < N; i++) {
        scanf("%c", &S[i]);
    }

    scanf("%d", &Q);

    for(int i = 0; i < Q; i++) {
        int l, r; scanf("%d %d", &l, &r);
        l--; r--;

        query[l].push_back(pii(r, i));
    }

    bit1.init();
    bit2.init();
    for(int i = 0; i < N; i++) {
        bit1.upd(i, N - 1, S[i] == 'C'? 1 : -1, 0, N - 1, 1);
        bit2.upd(0, i, S[i] == 'C'? 1 : -1, 0, N - 1, 1);
    }

    fw.init();
    for(int i = 0; i < N; i++) {
        while(1) {
            int t = bit1.kquer(0, 0, N - 1, 1);
            if(t == -1) break;
            bit1.upd(t, N - 1, 1, 0, N - 1, 1);
            bit2.upd(0, t, 1, 0, N - 1, 1);
            fw.upd(t, 1);
        }

        for(int j = 0; j < query[i].size(); j++) {
            int r = query[i][j].first;
            int id = query[i][j].second;
            int t = bit2.quer(i, r, 0, N - 1, 1).first - (r == N - 1? 0 : bit2.quer(r + 1, r + 1, 0, N - 1, 1).first);
            ans[id] = fw.quer(i, r) + (t < 0? -t : 0);
        }

        int t = bit1.quer(i, i, 0, N - 1, 1).first;
        bit1.upd(i, N - 1, -t, 0, N - 1, 1);
    }

    for(int i = 0; i < Q; i++) {
        printf("%d\n", ans[i]);
    }
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:123:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < query[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~~
election.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", &N);
     ~~~~~^~~~~~~~~~~~
election.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c", &S[i]);
         ~~~~~^~~~~~~~~~~~~
election.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
election.cpp:100:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int l, r; scanf("%d %d", &l, &r);
                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12408 KB Output is correct
2 Correct 16 ms 12436 KB Output is correct
3 Correct 16 ms 12648 KB Output is correct
4 Correct 16 ms 12648 KB Output is correct
5 Correct 16 ms 12648 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12408 KB Output is correct
2 Correct 16 ms 12436 KB Output is correct
3 Correct 16 ms 12648 KB Output is correct
4 Correct 16 ms 12648 KB Output is correct
5 Correct 16 ms 12648 KB Output is correct
6 Correct 193 ms 22164 KB Output is correct
7 Correct 162 ms 22596 KB Output is correct
8 Correct 180 ms 23604 KB Output is correct
9 Correct 187 ms 24868 KB Output is correct
10 Correct 188 ms 25776 KB Output is correct
11 Correct 197 ms 26948 KB Output is correct
12 Correct 184 ms 27944 KB Output is correct
13 Correct 197 ms 29076 KB Output is correct
14 Correct 186 ms 29968 KB Output is correct
15 Correct 176 ms 30776 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12408 KB Output is correct
2 Correct 16 ms 12436 KB Output is correct
3 Correct 16 ms 12648 KB Output is correct
4 Correct 16 ms 12648 KB Output is correct
5 Correct 16 ms 12648 KB Output is correct
6 Correct 193 ms 22164 KB Output is correct
7 Correct 162 ms 22596 KB Output is correct
8 Correct 180 ms 23604 KB Output is correct
9 Correct 187 ms 24868 KB Output is correct
10 Correct 188 ms 25776 KB Output is correct
11 Correct 197 ms 26948 KB Output is correct
12 Correct 184 ms 27944 KB Output is correct
13 Correct 197 ms 29076 KB Output is correct
14 Correct 186 ms 29968 KB Output is correct
15 Correct 176 ms 30776 KB Output is correct
16 Correct 1699 ms 93488 KB Output is correct
17 Correct 1320 ms 97360 KB Output is correct
18 Correct 1538 ms 105436 KB Output is correct
19 Correct 1479 ms 114544 KB Output is correct
20 Correct 1572 ms 122372 KB Output is correct
21 Correct 1597 ms 125000 KB Output is correct
22 Correct 1451 ms 125000 KB Output is correct
23 Correct 1612 ms 125088 KB Output is correct
24 Correct 1437 ms 125088 KB Output is correct
25 Correct 1400 ms 125088 KB Output is correct