Submission #563592

#TimeUsernameProblemLanguageResultExecution timeMemory
563592ngpin04Sweeping (JOI20_sweeping)C++14
0 / 100
6578 ms647288 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define TASK "" #define bit(x) (1LL << (x)) #define getbit(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() using namespace std; template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 2e6 + 5; const int oo = 1e9; const long long ooo = 1e18; const int mod = 1e9 + 7; // 998244353; const long double pi = acos(-1); struct trie { struct node { int cnt; int ptr[2]; node(int _cnt = 0) { cnt = _cnt; for (int i = 0; i < 2; i++) ptr[i] = 0; } }; vector <node> tree; int node,sz; #define ptr(cur, i) tree[cur].ptr[i] #define cnt(cur) tree[cur].cnt trie() { node = 0; sz = 0; tree.emplace_back(); } void add(int x, int val) { sz += val; int cur = 0; for (int i = 29; i >= 0; i--) { int v = getbit(x, i); if (ptr(cur, v)) { ptr(cur, v) = ++node; tree.emplace_back(); } cur = ptr(cur, v); cnt(cur)++; } } int getcnt(int x) { int cur = 0; int res = 0; for (int i = 29; i >= 0; i--) { int v = getbit(x, i); for (int j = 0; j < v; j++) res += cnt(ptr(cur, 0)); cur = ptr(cur, 1); if (cur == 0) break; } return res; } }; vector <trie> tx, ty; map <int, int> posx; set <pair <int, int>> sx[N], sy[N]; trie block[N]; int curx[N]; int cury[N]; int ind[N]; int bk[N]; int op[N]; int x[N]; int y[N]; int n,m,q,nDust,nBlock; void change(int i, int newb) { int curb = bk[i]; // cerr << i << " " << curb << " " << newb << "\n"; tx[curb].add(x[i], -1); ty[curb].add(y[i], -1); sx[curb].erase(mp(x[i], i)); sy[curb].erase(mp(y[i], i)); bk[i] = newb; tx[newb].add(x[i], 1); ty[newb].add(y[i], 1); sx[newb].insert(mp(x[i], i)); sy[newb].insert(mp(y[i], i)); } void sub1() { posx[0] = 0; tx.emplace_back(), ty.emplace_back(); for (int i = 1; i <= m; i++) { sx[0].insert(mp(x[i], i)); sy[0].insert(mp(y[i], i)); tx[0].add(x[i], 1); ty[0].add(y[i], 1); bk[i] = 0; } for (int i = m + 1; i <= q; i++) { // cerr << "query " << i << "\n"; if (op[i] == 1) { int id = ind[i]; cout << max(curx[bk[id]], x[id]) << " " << max(cury[bk[id]], y[id]) << "\n"; } else if (op[i] == 2) { int Lx = n - x[i]; int Ly = x[i]; // cerr << i << " " << Lx << " " << Ly << "\n"; if (posx.count(Lx) == 0) { int pre = prev(posx.lower_bound(Lx))->se; int up = ty[pre].getcnt(Ly + 1); int dn = ty[pre].sz - up; posx[Lx] = ++nBlock; curx[nBlock] = Lx; tx.emplace_back(); ty.emplace_back(); int cur = nBlock; if (up < dn) { while (sy[pre].size()) { auto it = prev(sy[pre].end()); if (y[it->se] <= Ly) break; // cerr << pre << " " << cur << " " << it->se << "\n"; change(it->se, cur); } swap(posx[Lx], posx[curx[pre]]); swap(curx[pre], curx[cur]); swap(cury[pre], cury[cur]); } else { while (sy[pre].size()) { auto it = sy[pre].begin(); if (y[it->se] > Ly) break; change(it->se, cur); } } } } else { // int Lx = x[i]; // int Ly = n - x[i]; // int pre = prev(posx.lower_bound(Lx))->se; // int lf = tx[pre].getcnt(Lx + 1); // int rt = tx[pre].sz - lf; // posx[Lx] = ++nBlock; // curx[nBlock] = Lx; // cury[pre] = Ly; // int cur = nBlock; // if (lf > rt) { // while (sx[pre].size()) { // auto it = prev(sx[pre].end()); // if (x[it->se] <= Lx) // break; // change(it->se, cur); // } // } else { // while (sx[pre].size()) { // auto it = sx[pre].begin(); // if (x[it->se] > Lx) // break; // change(it->se, cur); // } // swap(posx[Lx], posx[curx[pre]]); // swap(curx[pre], curx[cur]); // swap(cury[pre], cury[cur]); // } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef ONLINE_JUDGE // freopen(TASK".inp","r",stdin); // freopen(TASK".out","w",stdout); #endif cin >> n >> m >> q; for (int i = 1; i <= m; i++) { op[i] = 4; cin >> x[i] >> y[i]; } q += m; for (int i = m + 1; i <= q; i++) { cin >> op[i]; assert(op[i] <= 3); if (op[i] == 1) { cin >> ind[i]; } else if (op[i] <= 3) { cin >> x[i]; } else cin >> x[i] >> y[i]; } sub1(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...