Submission #251317

#	Time	Username	Problem	Language	Result	Execution time	Memory
251317		imeimi2000	Sweeping (JOI20_sweeping)	C++17	100 / 100	8715 ms	985208 KiB

sweeping

#include <bits/stdc++.h>

using namespace std;

int n, m, q;
int X[1500001], Y[1500001];
int T[1000001], A[1000001], B[1000001];

vector<int> cp;
int I[1500001];

struct point {
    mutable int * val;
    bool operator<(point p) const {
        return *val < *p.val;
    }
    operator int() const { return *val; }
} L[1500001], R[1500001];

struct node {
    map<point, vector<int>> L, R;
} seg[1 << 22];

point insert(map<point, vector<int>> &sp, int x, int p) {
    point v;
    v.val = &x;
    if (!sp.count(v)) {
        point p;
        p.val = new int(x);
        sp[p];
    }
    auto it = sp.find(v);
    it->second.push_back(p);
    return it->first;
}

void add_point(int i, int s, int e, int p) {
    if (s > e) return;
    if (X[p] < cp[s] || cp[e] < Y[p]) return;
    int m = (s + e) / 2;
    if (X[p] <= cp[m] && cp[m] <= Y[p]) {
        L[p] = insert(seg[i].L, X[p], p);
        R[p] = insert(seg[i].R, Y[p], p);
        I[p] = i;
        return;
    }
    add_point(i + i, s, m - 1, p);
    add_point(i + i + 1, m + 1, e, p);
}

void push_left(int i, int s, int e, int x) {
    if (s > e) return;
    if (cp[e] < x || x < cp[s]) return;
    int m = (s + e) / 2;
    if (x < cp[m]) {
        while (!seg[i].L.empty()) {
            auto &[y, p] = *seg[i].L.begin();
            if (y > x) break;
            for (int j : p) {
                if (I[j] != i) continue;
                X[j] = y;
                Y[j] = x;
                add_point(i + i, s, m - 1, j);
            }
            int * t = y.val;
            seg[i].L.erase(seg[i].L.begin());
            delete t;
        }
    }
    else {
        point v;
        v.val = new int;
        vector<int> g;
        while (!seg[i].R.empty()) {
            auto &[y, p] = *--seg[i].R.end();
            if (y < x) break;
            if (g.size() < p.size()) *(v.val) = *(y.val), swap(v.val, y.val), swap(g, p);
            for (int j : p) {
                if (I[j] != i) continue;
                R[j] = v;
                g.push_back(j);
            }
            int * t = y.val;
            seg[i].R.erase(--seg[i].R.end());
            delete t;
        }
        *(v.val) = x;
        swap(g, seg[i].R[v]);
    }
    push_left(i + i, s, m - 1, x);
    push_left(i + i + 1, m + 1, e, x);
}

void push_right(int i, int s, int e, int x) {
    if (s > e) return;
    if (cp[e] < x || x < cp[s]) return;
    int m = (s + e) / 2;
    if (x > cp[m]) {
        while (!seg[i].R.empty()) {
            auto &[y, p] = *--seg[i].R.end();
            if (y < x) break;
            for (int j : p) {
                if (I[j] != i) continue;
                X[j] = x;
                Y[j] = y;
                add_point(i + i + 1, m + 1, e, j);
            }
            int * t = y.val;
            seg[i].R.erase(--seg[i].R.end());
            delete t;
        }
    }
    else {
        point v;
        v.val = new int;
        vector<int> g;
        while (!seg[i].L.empty()) {
            auto &[y, p] = *seg[i].L.begin();
            if (y > x) break;
            if (g.size() < p.size()) *(v.val) = *(y.val), swap(v.val, y.val), swap(g, p);
            for (int j : p) {
                if (I[j] != i) continue;
                L[j] = v;
                g.push_back(j);
            }
            int * t = y.val;
            seg[i].L.erase(seg[i].L.begin());
            delete t;
        }
        *(v.val) = x;
        swap(g, seg[i].L[v]);
    }
    push_right(i + i, s, m - 1, x);
    push_right(i + i + 1, m + 1, e, x);
}

int main() {
    //freopen(R"(c:\Users\imeim\Documents\VSCode\oi\joisc20\sweeping.txt)", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i) {
        cin >> X[i] >> Y[i];
        Y[i] = n - Y[i];
        cp.push_back(X[i]);
        cp.push_back(Y[i]);
    }
    for (int i = 1; i <= q; ++i) {
        cin >> T[i] >> A[i];
        if (T[i] == 2) A[i] = n - A[i];
        if (T[i] == 2 || T[i] == 3)
            cp.push_back(A[i]);
        if (T[i] == 4) {
            cin >> B[i];
            B[i] = n - B[i];
            cp.push_back(A[i]);
            cp.push_back(B[i]);
        }
    }
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    int l = n;
    n = int(cp.size()) - 1;
    for (int i = 1; i <= m; ++i) add_point(1, 0, n, i);
    for (int it = 1; it <= q; ++it) {
        if (T[it] == 1) {
            printf("%d %d\n", int(L[A[it]]), l - int(R[A[it]]));
        }
        if (T[it] == 2) {
            push_right(1, 0, n, A[it]);
        }
        if (T[it] == 3) {
            push_left(1, 0, n, A[it]);
        }
        if (T[it] == 4) {
            int i = ++m;
            X[i] = A[it];
            Y[i] = B[it];
            add_point(1, 0, n, i);
        }
    }
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25