oj.uz

Submission #212613

# Submission time Handle Problem Language Result Execution time Memory
212613 2020-03-23T20:09:30 Z egorlifar Sweeping (JOI20_sweeping) C++17
100 / 100
 9882 ms 1240184 KB 
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#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 = 200 * 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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3072 KB Output is correct
2 Correct 24 ms 2128 KB Output is correct
3 Correct 10 ms 1920 KB Output is correct
4 Correct 25 ms 2944 KB Output is correct
5 Correct 23 ms 3200 KB Output is correct
6 Correct 8 ms 2048 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7662 ms 474880 KB Output is correct
2 Correct 7506 ms 475648 KB Output is correct
3 Correct 7514 ms 494920 KB Output is correct
4 Correct 6879 ms 702880 KB Output is correct
5 Correct 8141 ms 505940 KB Output is correct
6 Correct 8548 ms 608608 KB Output is correct
7 Correct 7394 ms 475404 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6973 ms 561192 KB Output is correct
2 Correct 7060 ms 565984 KB Output is correct
3 Correct 6292 ms 647356 KB Output is correct
4 Correct 6635 ms 975140 KB Output is correct
5 Correct 7385 ms 824964 KB Output is correct
6 Correct 6850 ms 564328 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6973 ms 561192 KB Output is correct
2 Correct 7060 ms 565984 KB Output is correct
3 Correct 6292 ms 647356 KB Output is correct
4 Correct 6635 ms 975140 KB Output is correct
5 Correct 7385 ms 824964 KB Output is correct
6 Correct 6850 ms 564328 KB Output is correct
7 Correct 7561 ms 527668 KB Output is correct
8 Correct 7643 ms 551080 KB Output is correct
9 Correct 7613 ms 503784 KB Output is correct
10 Correct 7631 ms 634220 KB Output is correct
11 Correct 7768 ms 850368 KB Output is correct
12 Correct 9217 ms 662556 KB Output is correct
13 Correct 9057 ms 1118324 KB Output is correct
14 Correct 432 ms 203936 KB Output is correct
15 Correct 1636 ms 318012 KB Output is correct
16 Correct 7428 ms 544972 KB Output is correct
17 Correct 7728 ms 565252 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3072 KB Output is correct
2 Correct 24 ms 2128 KB Output is correct
3 Correct 10 ms 1920 KB Output is correct
4 Correct 25 ms 2944 KB Output is correct
5 Correct 23 ms 3200 KB Output is correct
6 Correct 8 ms 2048 KB Output is correct
7 Correct 7662 ms 474880 KB Output is correct
8 Correct 7506 ms 475648 KB Output is correct
9 Correct 7514 ms 494920 KB Output is correct
10 Correct 6879 ms 702880 KB Output is correct
11 Correct 8141 ms 505940 KB Output is correct
12 Correct 8548 ms 608608 KB Output is correct
13 Correct 7394 ms 475404 KB Output is correct
14 Correct 6973 ms 561192 KB Output is correct
15 Correct 7060 ms 565984 KB Output is correct
16 Correct 6292 ms 647356 KB Output is correct
17 Correct 6635 ms 975140 KB Output is correct
18 Correct 7385 ms 824964 KB Output is correct
19 Correct 6850 ms 564328 KB Output is correct
20 Correct 7561 ms 527668 KB Output is correct
21 Correct 7643 ms 551080 KB Output is correct
22 Correct 7613 ms 503784 KB Output is correct
23 Correct 7631 ms 634220 KB Output is correct
24 Correct 7768 ms 850368 KB Output is correct
25 Correct 9217 ms 662556 KB Output is correct
26 Correct 9057 ms 1118324 KB Output is correct
27 Correct 432 ms 203936 KB Output is correct
28 Correct 1636 ms 318012 KB Output is correct
29 Correct 7428 ms 544972 KB Output is correct
30 Correct 7728 ms 565252 KB Output is correct
31 Correct 8089 ms 640452 KB Output is correct
32 Correct 7979 ms 505616 KB Output is correct
33 Correct 8379 ms 460156 KB Output is correct
34 Correct 7847 ms 567260 KB Output is correct
35 Correct 7834 ms 515708 KB Output is correct
36 Correct 7436 ms 618492 KB Output is correct
37 Correct 9777 ms 1046684 KB Output is correct
38 Correct 9882 ms 1240184 KB Output is correct
39 Correct 9519 ms 981144 KB Output is correct
40 Correct 7475 ms 572460 KB Output is correct