Submission #268391

#	Time	Username	Problem	Language	Result	Execution time	Memory
268391		imeimi2000	Interval Collection (CCO20_day2problem2)	C++17	25 / 25	1469 ms	198260 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e8, n = 1e6;
template <int X>
struct PQ {
    priority_queue<int> pq1, pq2;
    void push(int x) {
        pq1.push(x * X);
    }
    void pop(int x) {
        pq2.push(x * X);
        while (!pq2.empty() && pq1.top() == pq2.top()) {
            pq1.pop();
            pq2.pop();
        }
    }
    int top() {
        if (pq1.empty()) return -inf * X;
        return pq1.top() * X;
    }
};

const int sz = 1 << 20;
PQ<1> L[sz], Ls;
PQ<-1> R[sz], Rs;

struct node {
    int l, r, m;
    void init(int i) {
        l = L[i].top();
        r = R[i].top();
        m = r - l;
    }
    node operator+(const node &p) const {
        node ret;
        ret.l = max(l, p.l);
        ret.r = min(r, p.r);
        ret.m = min({ m, p.m, p.r - l });
        return ret;
    }
} seg[sz << 1];

void update(int i) {
    seg[i + sz].init(i);
    i += sz;
    while (i >>= 1) seg[i] = seg[i + i] + seg[i + i + 1];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int q;
    cin >> q;
    for (int i = 0; i < sz; ++i) seg[i + sz].init(i);
    for (int i = sz; i--; ) seg[i] = seg[i + i] + seg[i + i + 1];
    while (q--) {
        char C[10];
        int l, r;
        cin >> C >> l >> r;
        if (C[0] == 'A') {
            Ls.push(l);
            Rs.push(r);
            L[r].push(l);
            R[l].push(r);
        }
        else {
            Ls.pop(l);
            Rs.pop(r);
            L[r].pop(l);
            R[l].pop(r);
        }
        update(l), update(r);
        if (Ls.top() < Rs.top()) {
            printf("%d\n", R[Ls.top()].top() - L[Rs.top()].top());
            continue;
        }
        printf("%d\n", seg[1].m);
    }
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 4 / 4
• Subtask 5: 3 / 3