Submission #563489

#	Time	Username	Problem	Language	Result	Execution time	Memory
563489		hoanghq2004	Sweeping (JOI20_sweeping)	C++14	0 / 100	6289 ms	333784 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] = m - L;
    Y[cnt_block] = Y[get<2>(*iter)];
    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});
    }
    ranges.insert({get<0>(*iter), L, cnt_block});
    ranges.insert({L, get<1>(*iter), id});
    ranges.erase(iter);
}

void DivideY(int id, int L, auto iter) {
    ++cnt_block;
    X[cnt_block] = X[get<2>(*iter)];
    Y[cnt_block] = 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});
    }
    ranges.insert({get<0>(*iter), m - L, id});
    ranges.insert({m - L, get<1>(*iter), cnt_block});
    ranges.erase(iter);
}

int main() {
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    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;
            auto iter = --ranges.lower_bound({L, (int)1e9, 0});
            if (get<0>(*iter) == L) {
                X[get<2>(*iter)] = max(X[get<2>(*iter)], m - L);
                if (iter != ranges.begin()) {
                    --iter;
                    X[get<2>(*iter)] = max(X[get<2>(*iter)], m - L);
                }
                continue;
            }
            DivideX(get<2>(*iter), L, iter);
        } else if (cmd == 3) {
            int L;
            cin >> L;
            auto iter = --ranges.lower_bound({m - L, (int)1e9, 0});
            if (get<0>(*iter) == m - L) {
                Y[get<2>(*iter)] = max(Y[get<2>(*iter)], m - L);
                if (iter != ranges.begin()) {
                    --iter;
                    Y[get<2>(*iter)] = max(Y[get<2>(*iter)], m - L);
                }
                continue;
            }
            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:51:29: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   51 | void DivideY(int id, int L, auto iter) {
      |                             ^~~~
sweeping.cpp: In function 'void DivideY(int, int, auto:2)':
sweeping.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |         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