Submission #130142

#	Time	Username	Problem	Language	Result	Execution time	Memory
130142		choikiwon	Worst Reporter 2 (JOI16_worst_reporter2)	C++17	0 / 100	2059 ms	27000 KiB

worst_reporter2

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

typedef pair<int, int> pii;

const int MN = 200010;

int N;
vector<int> V[MN], X[MN];
priority_queue<int> freeV;
multiset<int> freeX;

int Cn;
vector<int> C;
unordered_map<int, int> dc;

struct BIT {
    int Z;
    vector<pii> tree;
    vector<int> lazy;
    void init(int Z_) {
        Z = Z_;
        tree = vector<pii>(4 * Z);
        lazy = vector<int>(4 * Z, 0);
        build(0, Z - 1, 1);
    }
    void build(int l, int r, int n) {
        if(l == r) {
            tree[n] = {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);
    }
    void upd(int a, int b, int d) { upd(a, b, d, 0, Z - 1, 1); }
    pii quer(int a, int b) { return quer(a, b, 0, Z - 1, 1); }
};

struct RMQ {
    int Z;
    vector<int> tree;
    void init(int Z_) {
        Z = Z_;
        tree = vector<int>(4 * Z);
        build(0, Z - 1, 1);
    }
    void build(int l, int r, int n) {
        if(l == r) {
            tree[n] = l;
            return;
        }
        int m = (l + r)>>1;
        build(l, m, 2*n);
        build(m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    void upd(int x, int v, int l, int r, int n) {
        if(x < l || r < x) return;
        if(l == r) {
            tree[n] = v;
            return;
        }
        int m = (l + r)>>1;
        upd(x, v, l, m, 2*n);
        upd(x, v, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    void upd(int x, int v) { upd(x, v, 0, Z - 1, 1); }
};

BIT bit[MN];
RMQ rmq[MN];

struct Info {
    int v, i, j, l;
    bool operator <(const Info &i) const {
        return v < i.v;
    }
};
priority_queue<Info> cand, pq;
vector<Info> P;
int la[MN];

void relax() {
    while(!cand.empty()) {
        Info t = cand.top();

        int x = t.j;
        if(t.l != la[x]) {
            cand.pop();
            continue;
        }
        break;
    }
}

int main() {
    std::ios::sync_with_stdio(false);

    cin >> N;

    for(int i = 0; i < N; i++) {
        int a, b; cin >> a >> b;
        V[--a].push_back(b);
    }
    for(int i = 0; i < N; i++) {
        int c, d; cin >> c >> d;
        X[--c].push_back(d);
    }

    int ans = 0;
    for(int i = 0; i < N; i++) {
        sort(V[i].begin(), V[i].end());
        sort(X[i].begin(), X[i].end());

        vector<int> chk(V[i].size(), 0);
        vector<int> tmp;

        int pos = (int)X[i].size() - 1;
        for(int j = (int)V[i].size() - 1; j >= 0; j--) {
            if(pos >= 0 && V[i][j] <= X[i][pos]) {
                pos--;
                continue;
            }
            freeV.push(V[i][j]);
            chk[j] = 1;
        }
        for(int j = 0; j < V[i].size(); j++) if(!chk[j]) tmp.push_back(V[i][j]);
        V[i] = tmp;

        if(V[i].size() == 0) {
            for(int j = 0; j < X[i].size(); j++) {
                freeX.insert(X[i][j]);
            }
            la[i] = -1;
            continue;
        }

        bit[i].init(V[i].size());
        rmq[i].init(V[i].size());

        chk = vector<int>(X[i].size(), 0);

        pos = 0;
        for(int j = 0; j < V[i].size(); j++) {
            while(pos < X[i].size() && X[i][pos] < V[i][j]) pos++;
            chk[pos] = 1;
            pos++;

            P.push_back({V[i][j], i, j});
        }

        tmp.clear();
        for(int j = 0; j < X[i].size(); j++) {
            if(chk[j]) tmp.push_back(X[i][j]);
            else freeX.insert(X[i][j]);
        }
        X[i] = tmp;

        pos = (int)X[i].size() - 1;
        for(int j = (int)V[i].size() - 1; j >= 0; j--) {
            while(pos >= 0 && X[i][pos] >= V[i][j]) pos--;
            bit[i].upd(j, j, j - pos);
        }

        pii t = bit[i].tree[1];
        pq.push({ X[i].back(), V[i][-t.second], i });
        la[i] = (int)V[i].size() - 1;
    }

    ans += freeV.size();

    sort(P.begin(), P.end());

    int pos = (int)P.size() - 1;
    while(!freeV.empty()) {
        int v = freeV.top(); freeV.pop();

        while(pos >= 0 && P[pos].v >= v) {
            int x = P[pos].i;
            if(P[pos].j != la[x]) {
                pos--;
                continue;
            }

            bit[x].upd(la[x], la[x], 1e9);
            rmq[x].upd(la[x], -1);
            la[x] = rmq[x].tree[1];

            if(la[x] >= 0) {
                pii t = bit[x].tree[1];
                pq.push({ X[x][ la[x] ], V[x][-t.second], x, la[x] });
            }
            pos--;
        }
        while(!pq.empty() && pq.top().v >= v) {
            Info t = pq.top(); pq.pop();
            cand.push({ -t.i, t.v, t.j });
        }

        auto it = freeX.lower_bound(v);
        if(it != freeX.end()) {
            freeX.erase(it);
            continue;
        }

        ans++;
        relax();

        Info t = cand.top(); cand.pop();

        int x = t.j;
        int s = lower_bound(V[x].begin(), V[x].end(), t.i) - V[x].begin();
        int e = la[x];

        bit[x].upd(s, e, -1);
        bit[x].upd(s, s, 1e9);
        bit[x].upd(e, e, 1e9);
        rmq[x].upd(s, -1);
        rmq[x].upd(e, -1);
        la[x] = rmq[x].tree[1];

        if(la[x] >= 0) {
            pii t = bit[x].tree[1];
            pq.push({ X[x][ la[x] ], V[x][-t.second], x, la[x] });
        }

        freeV.push(V[x][s]);
    }

    cout << ans;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:161:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < V[i].size(); j++) if(!chk[j]) tmp.push_back(V[i][j]);
                        ~~^~~~~~~~~~~~~
worst_reporter2.cpp:165:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < X[i].size(); j++) {
                            ~~^~~~~~~~~~~~~
worst_reporter2.cpp:178:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < V[i].size(); j++) {
                        ~~^~~~~~~~~~~~~
worst_reporter2.cpp:179:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(pos < X[i].size() && X[i][pos] < V[i][j]) pos++;
                   ~~~~^~~~~~~~~~~~~
worst_reporter2.cpp:187:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < X[i].size(); j++) {
                        ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40