Submission #563549

#	Time	Username	Problem	Language	Result	Execution time	Memory
563549		hoanghq2004	Sweeping (JOI20_sweeping)	C++14	0 / 100	6389 ms	333828 KiB

sweeping

#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];

struct Point {
    int x, y, i;
    int operator < (const Point& other) const {
        if (x ^ other.x) return x < other.x;
        if (y ^ other.y) return y < other.y;
        return i < other.i;
    }
} P[N];

set <Point> bX[N], bY[N];

int cnt_block = 1;
set <tuple <int, int, int> > ranges;
int block[N];

void DivideX(int id, int L, auto iter) {
    ++cnt_block;
    X[cnt_block] = max(X[id], m - L);
    Y[cnt_block] = Y[id];
    while (bY[id].size()) {
        auto [x, y, i] = *bY[id].begin();
        if (x > L) break;
        block[i] = cnt_block;
        bY[id].erase({x, y, i});
        bX[id].erase({y, x, i});
        bY[cnt_block].insert({x, y, i});
        bX[cnt_block].insert({y, x, i});
    }
    int lft = get<0>(*iter);
    int rgt = get<1>(*iter);
    ranges.erase(iter);
    ranges.insert({lft, L + 1, cnt_block});
    ranges.insert({L + 1, rgt, id});
}

void DivideY(int id, int L, auto iter) {
    ++cnt_block;
    X[cnt_block] = X[id];
    Y[cnt_block] = max(Y[id], m - L);
    while (bX[id].size()) {
        auto [x, y, i] = *bX[id].begin();
        if (x > L) break;
        block[i] = cnt_block;
        bX[id].erase({x, y, i});
        bY[id].erase({y, x, i});
        bX[cnt_block].insert({x, y, i});
        bY[cnt_block].insert({y, x, i});
    }
    int lft = get<0>(*iter);
    int rgt = get<1>(*iter);
    ranges.erase(iter);
    ranges.insert({lft, m - L, id});
    ranges.insert({m - L, rgt, cnt_block});
}

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, i};
        bX[cnt_block].insert({x, y, i});
        bY[cnt_block].insert({y, x, i});
    }
    ranges.insert({0, m, 1});
    while (q--) {
        int cmd;
        cin >> cmd;
        if (cmd == 1) {
            int i;
            cin >> i;
            cout << max(P[i].x, X[block[i]]) << ' ' << max(P[i].y, Y[block[i]]) << '\n';
        } else if (cmd == 2) {
            int L;
            cin >> L;
            if (L == 0 || L == m) continue;
            auto iter = --ranges.lower_bound({L + 1, -1, 0});
            DivideX(get<2>(*iter), L, iter);
        } else if (cmd == 3) {
            int L;
            cin >> L;
            if (L == 0 || L == m) continue;
            auto iter = --ranges.lower_bound({m - L, -1, 0});
            if (get<1>(*iter) == m - L) assert(get<0>(*iter) != m - L);
            DivideY(get<2>(*iter), L, iter);
        } else {
            assert(0);
        }
    }
}

Compilation message (stderr)

sweeping.cpp:33:29: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   33 | void DivideX(int id, int L, auto iter) {
      |                             ^~~~
sweeping.cpp: In function 'void DivideX(int, int, auto:1)':
sweeping.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         auto [x, y, i] = *bY[id].begin();
      |              ^
sweeping.cpp: At global scope:
sweeping.cpp:53:29: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   53 | void DivideY(int id, int L, auto iter) {
      |                             ^~~~
sweeping.cpp: In function 'void DivideY(int, int, auto:2)':
sweeping.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         auto [x, y, i] = *bX[id].begin();
      |              ^

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