oj.uz

Submission #251317

# Submission time Handle Problem Language Result Execution time Memory
251317 2020-07-20T18:42:37 Z imeimi2000 Sweeping (JOI20_sweeping) C++17
100 / 100
 8715 ms 985208 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 395516 KB Output is correct
2 Correct 234 ms 395256 KB Output is correct
3 Correct 251 ms 395768 KB Output is correct
4 Correct 258 ms 395256 KB Output is correct
5 Correct 218 ms 395128 KB Output is correct
6 Correct 213 ms 394616 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7471 ms 692604 KB Output is correct
2 Correct 6794 ms 693140 KB Output is correct
3 Correct 6458 ms 692828 KB Output is correct
4 Correct 5680 ms 985208 KB Output is correct
5 Correct 7325 ms 651956 KB Output is correct
6 Correct 8715 ms 665240 KB Output is correct
7 Correct 6389 ms 692192 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5089 ms 602056 KB Output is correct
2 Correct 4773 ms 594528 KB Output is correct
3 Correct 3803 ms 903116 KB Output is correct
4 Correct 3572 ms 612784 KB Output is correct
5 Correct 5038 ms 603932 KB Output is correct
6 Correct 4411 ms 592852 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5089 ms 602056 KB Output is correct
2 Correct 4773 ms 594528 KB Output is correct
3 Correct 3803 ms 903116 KB Output is correct
4 Correct 3572 ms 612784 KB Output is correct
5 Correct 5038 ms 603932 KB Output is correct
6 Correct 4411 ms 592852 KB Output is correct
7 Correct 6130 ms 650756 KB Output is correct
8 Correct 6308 ms 650008 KB Output is correct
9 Correct 5837 ms 650216 KB Output is correct
10 Correct 5270 ms 904564 KB Output is correct
11 Correct 5453 ms 610016 KB Output is correct
12 Correct 6580 ms 600168 KB Output is correct
13 Correct 7006 ms 604508 KB Output is correct
14 Correct 512 ms 410208 KB Output is correct
15 Correct 2386 ms 509668 KB Output is correct
16 Correct 6428 ms 650852 KB Output is correct
17 Correct 6337 ms 650572 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 395516 KB Output is correct
2 Correct 234 ms 395256 KB Output is correct
3 Correct 251 ms 395768 KB Output is correct
4 Correct 258 ms 395256 KB Output is correct
5 Correct 218 ms 395128 KB Output is correct
6 Correct 213 ms 394616 KB Output is correct
7 Correct 7471 ms 692604 KB Output is correct
8 Correct 6794 ms 693140 KB Output is correct
9 Correct 6458 ms 692828 KB Output is correct
10 Correct 5680 ms 985208 KB Output is correct
11 Correct 7325 ms 651956 KB Output is correct
12 Correct 8715 ms 665240 KB Output is correct
13 Correct 6389 ms 692192 KB Output is correct
14 Correct 5089 ms 602056 KB Output is correct
15 Correct 4773 ms 594528 KB Output is correct
16 Correct 3803 ms 903116 KB Output is correct
17 Correct 3572 ms 612784 KB Output is correct
18 Correct 5038 ms 603932 KB Output is correct
19 Correct 4411 ms 592852 KB Output is correct
20 Correct 6130 ms 650756 KB Output is correct
21 Correct 6308 ms 650008 KB Output is correct
22 Correct 5837 ms 650216 KB Output is correct
23 Correct 5270 ms 904564 KB Output is correct
24 Correct 5453 ms 610016 KB Output is correct
25 Correct 6580 ms 600168 KB Output is correct
26 Correct 7006 ms 604508 KB Output is correct
27 Correct 512 ms 410208 KB Output is correct
28 Correct 2386 ms 509668 KB Output is correct
29 Correct 6428 ms 650852 KB Output is correct
30 Correct 6337 ms 650572 KB Output is correct
31 Correct 5270 ms 634520 KB Output is correct
32 Correct 6294 ms 669364 KB Output is correct
33 Correct 4495 ms 734708 KB Output is correct
34 Correct 6842 ms 699344 KB Output is correct
35 Correct 7040 ms 699876 KB Output is correct
36 Correct 5674 ms 851540 KB Output is correct
37 Correct 7334 ms 642488 KB Output is correct
38 Correct 6701 ms 611600 KB Output is correct
39 Correct 6605 ms 612340 KB Output is correct
40 Correct 5972 ms 657940 KB Output is correct