Submission #212620

#	Time	Username	Problem	Language	Result	Execution time	Memory
212620		egorlifar	Sweeping (JOI20_sweeping)	C++17	1 / 100	234 ms	96248 KiB

sweeping

/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <array>
       
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
const int MAXMEM = 50 * 1000 * 1024;
char _memory[MAXMEM];
size_t _ptr = 0;
void* operator new(size_t _x) { _ptr += _x; return _memory + _ptr - _x; }
void operator delete (void*) noexcept {}
const string FILENAME = "input";
const int MAXN = 1500228;


int parent[MAXN * 2];


struct dsu {
    vector<int> val; 
    vector<vector<int> > realParent;
    void init() { 
        val.clear(); 
        realParent.clear(); 
    }
    int add(int v, int col) {
        int id = sz(val); 
        val.pb(v); 
        realParent.emplace_back();
        if (col != -1) {
            parent[col] = id;
            realParent.back().pb(col);
        }
        return id;
    }
    int unite(int x, int y) {
        if (sz(realParent[x]) < sz(realParent[y])) {
            swap(x, y);
        }
        chkmax(val[x], val[y]);
        for (auto &t: realParent[y]) {
            parent[t] = x;
            realParent[x].pb(t);
        }
        return x;
    }
    int get(int x) { 
        return val[parent[x]]; 
    }
};


dsu tr;


struct comp {
    bool operator()(const int a, const int b) { 
        return tr.val[a] > tr.val[b]; 
    }
};


int xpos[MAXN], ypos[MAXN];


pair<int, int> getPos(int x) { 
    return mp(tr.get(2 * x), tr.get(2 * x + 1)); 
}


int n, m, q;
bool was[MAXN];
pair<int, int> ans[MAXN], pos[MAXN];


void solve(int x, int y, vector<vector<int> > v) {
    if (v.empty()) {
        return;
    }
    int dif = n - x - y;
    if (dif == 0) {
        for (auto &t: v) { 
            if (t[0] == 1) {
                ans[t[2]] = {x, y};
            }
        }
        return;
    }
    tr.init(); 
    int X = x + (dif + 1) / 2, Y = y + dif / 2 + 1;
    vector<vector<int> > upper, right;
    priority_queue<int, vector<int>, comp> qx, qy;
    for (auto &t: v) {
        if (t[0] == 1) {
            if (pos[t[1]].second >= Y) {
                upper.pb(t);
            } else if (pos[t[1]].first >= X) {
                right.pb(t);
            } else {
                ans[t[2]] = getPos(t[1]);
            }
        } else if (t[0] == 2) { 
            if (t[1] >= Y) {
                int z = n - t[1]; 
                int as = tr.add(z, -1);
                while (sz(qx) && tr.val[qx.top()] < z) {
                    int x = qx.top(); 
                    qx.pop();
                    as = tr.unite(as, x);
                }
                qx.push(as); 
                upper.pb(t);
            } else {
                while (sz(qy) && tr.val[qy.top()] <= t[1]) {
                    int x = qy.top(); 
                    qy.pop(); 
                    for (auto &u: tr.realParent[x]) {
                        u /= 2;
                        if (!was[u]) {
                            pos[u] = getPos(u); 
                            pos[u].first = n - t[1]; 
                            was[u] = 1; 
                            right.pb({4, u, -1});
                        }
                    }
                }
                right.pb(t);
            }
        } else if (t[0] == 3) {
            if (t[1] >= X) {
                int z = n - t[1];
                int as = tr.add(z, -1);
                while (sz(qy) && tr.val[qy.top()] < z) {
                    int x = qy.top(); 
                    qy.pop();
                    as = tr.unite(as, x);
                }
                qy.push(as); 
                right.pb(t);
            } else {
                while (sz(qx) && tr.val[qx.top()] <= t[1]) {
                    int x = qx.top(); qx.pop(); 
                    for (auto &u: tr.realParent[x]) {
                        u /= 2;
                        if (!was[u]) {
                            pos[u] = getPos(u); 
                            pos[u].second = n - t[1]; 
                            was[u] = 1; 
                            upper.pb({4, u, -1});
                        }
                    }
                }
                upper.pb(t);
            }
        } else if (t[0] == 4) {
            was[t[1]] = 0; 
            pair<int, int> p = pos[t[1]];
            if (p.second >= Y) {
                was[t[1]] = 1;
                upper.pb(t);
            } else if (p.first >= X) {
                was[t[1]] = 1;
                right.pb(t);
            } else {
                qx.push(tr.add(p.first, 2 * t[1]));
                qy.push(tr.add(p.second, 2 * t[1] + 1));
            }
        }
    }
    solve(x, Y, upper); 
    solve(X, y, right);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  //  read(FILENAME); 
    cin >> n >> m >> q;
    int cnt = 0;
    vector<vector<int> > cur;
    for (int i = 0; i < m; i++) {
        int x, y; 
        cin >> x >> y;
        pos[++cnt] = {x ,y};
        cur.pb({4, cnt, 0});
    }
    for (int i = 0; i < q; i++) {
        ans[i] = {-1, -1};
        int t; 
        cin >> t;
        if (t <= 3) {
            int p; 
            cin >> p;
            cur.pb({t, p, i});
        } else {
            int a, b; 
            cin >> a >> b;
            pos[++cnt] = {a, b};
            cur.pb({t, cnt, i});
        }
    }
    solve(0, 0, cur);
    for (int i = 0; i < q; i++) {
        if (ans[i] != mp(-1, -1)) {
            cout << ans[i].first << ' ' << ans[i].second << '\n';
        }
    }
    return 0;       
}

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