Submission #268288

#	Time	Username	Problem	Language	Result	Execution time	Memory
268288		imeimi2000	Interval Collection (CCO20_day2problem2)	C++17	25 / 25	4670 ms	221212 KiB

Main

#include <bits/stdc++.h>

using namespace std;

multiset<int> L[1000001], R[1000001];

const int inf = 1e8, n = 1e6;
struct node {
    int l, r, m;
    void init(int i) {
        l = L[i].empty() ? -inf : *L[i].rbegin();
        r = R[i].empty() ? inf : *R[i].begin();
        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[1 << 21];

void init(int i, int s, int e) {
    if (s == e) {
        seg[i].init(s);
        return;
    }
    int m = (s + e) / 2;
    init(i + i, s, m);
    init(i + i + 1, m + 1, e);
    seg[i] = seg[i + i] + seg[i + i + 1];
}

void update(int i, int s, int e, int x) {
    if (s == e) {
        seg[i].init(x);
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) update(i + i, s, m, x);
    else update(i + i + 1, m + 1, e, x);
    seg[i] = seg[i + i] + seg[i + i + 1];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int q;
    cin >> q;
    multiset<int> Ls, Rs;
    init(1, 1, n);
    while (q--) {
        char C[10];
        int l, r;
        cin >> C >> l >> r;
        if (C[0] == 'A') {
            Ls.insert(l);
            Rs.insert(r);
            L[r].insert(l);
            R[l].insert(r);
        }
        else {
            Ls.erase(Ls.find(l));
            Rs.erase(Rs.find(r));
            L[r].erase(L[r].find(l));
            R[l].erase(R[l].find(r));
        }
        update(1, 1, n, l);
        update(1, 1, n, r);
        if (*Ls.rbegin() < *Rs.begin()) {
            printf("%d\n", *R[*Ls.rbegin()].begin() - *L[*Rs.begin()].rbegin());
            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