oj.uz

Submission #563564

# Submission time Handle Problem Language Result Execution time Memory
563564 2022-05-17T14:01:51 Z hoanghq2004 Sweeping (JOI20_sweeping) C++14
64 / 100
 5423 ms 520680 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e6 + 10;

int n, m, q;
int X[N], Y[N];
pair <int, int> P[N];
int block[N];
map <int, int> range;
ordered_set <pair <int, int> > bX[N], bY[N];

void add(int i, int b) {
    int _b = block[i];
    bX[_b].erase({P[i].first, i});
    bY[_b].erase({P[i].second, i});
    block[i] = b;
    bX[b].insert({P[i].first, i});
    bY[b].insert({P[i].second, i});
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> m >> n >> q;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        P[i] = {x, y};
        bX[0].insert({x, i});
        bY[0].insert({y, i});
    }
    range[0] = 0;
    for (int i = 1; i <= q; ++i) {
        int cmd;
        cin >> cmd;
        if (cmd == 1) {
            int id;
            cin >> id;
            cout << max(P[id].first, X[block[id]]) << ' ' << max(P[id].second, Y[block[id]]) << '\n';
        } else if (cmd == 2) {
            int L;
            cin >> L;
            if (range.find(m - L) == range.end()) {
                int j = (--range.lower_bound(m - L)) -> second;
                range[m - L] = i;
                X[i] = m - L, Y[i] = Y[j], Y[j] = L + 1;
                if (bY[j].order_of_key({L + 1, 0}) <= bY[j].size() / 2) {
                    while (bY[j].size() && bY[j].begin() -> first <= L) {
                        add(bY[j].begin() -> second, i);
                    }
                } else {
                    while (bY[j].size() && (--bY[j].end()) -> first > L) {
                        add((--bY[j].end()) -> second, i);
                    }
                    swap(X[i], X[j]), swap(Y[i], Y[j]), swap(range[X[i]], range[X[j]]);
                }
            }
        } else if (cmd == 3) {
            int L;
            cin >> L;
            if (range.find(L + 1) == range.end()) {
                int j = (--range.lower_bound(L + 1)) -> second;
                range[L + 1] = i;
                X[i] = L + 1, Y[i] = Y[j], Y[j] = m - L;
                if (bX[j].order_of_key({L + 1, 0}) <= bX[j].size() / 2) {
                    while (bX[j].size() && bX[j].begin() -> first <= L) {
                        add(bX[j].begin() -> second, i);
                    }
                    swap(X[i], X[j]), swap(Y[i], Y[j]), swap(range[X[i]], range[X[j]]);
                } else {
                    while (bX[j].size() && (--bX[j].end()) -> first > L) {
                        add((--bX[j].end()) -> second, i);
                    }
                }
            }
        } else {
            assert(0);
        }
    }
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 294 ms 381864 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2338 ms 520680 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3497 ms 297804 KB Output is correct
2 Correct 2878 ms 297756 KB Output is correct
3 Correct 1820 ms 298284 KB Output is correct
4 Correct 1735 ms 316784 KB Output is correct
5 Correct 3021 ms 317120 KB Output is correct
6 Correct 3066 ms 317556 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3497 ms 297804 KB Output is correct
2 Correct 2878 ms 297756 KB Output is correct
3 Correct 1820 ms 298284 KB Output is correct
4 Correct 1735 ms 316784 KB Output is correct
5 Correct 3021 ms 317120 KB Output is correct
6 Correct 3066 ms 317556 KB Output is correct
7 Correct 5423 ms 317724 KB Output is correct
8 Correct 5267 ms 317680 KB Output is correct
9 Correct 4969 ms 317596 KB Output is correct
10 Correct 2780 ms 316512 KB Output is correct
11 Correct 2426 ms 317468 KB Output is correct
12 Correct 4117 ms 317672 KB Output is correct
13 Correct 3812 ms 317624 KB Output is correct
14 Correct 233 ms 192168 KB Output is correct
15 Correct 1616 ms 280504 KB Output is correct
16 Correct 5236 ms 317584 KB Output is correct
17 Correct 4752 ms 313892 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 294 ms 381864 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -