Submission #90441

#	Time	Username	Problem	Language	Result	Execution time	Memory
90441		choikiwon	Election (BOI18_election)	C++17	100 / 100	1699 ms	125088 KiB

election

#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 (stderr)

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 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18