Submission #768429

#TimeUsernameProblemLanguageResultExecution timeMemory
768429minhcoolSweeping (JOI20_sweeping)C++17
0 / 100
18078 ms2097152 KiB
#define local #ifndef local #include "" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 5e5 + 5; const int oo = 1e18 + 7, mod = 1e9 + 7; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } int n, m, q; int x[N], y[N]; int type[N], width[N]; ii answer[N]; vector<ii> asks[N];// ask which node, after which query? vector<int> queries[N];// queries like "we start from query i, we ask for this node" set<int> IT1[N << 2], IT2[N << 2]; void upd1(int id, int l, int r, int pos, int val, bool add){ if(add) IT1[id].insert(val); else IT1[id].erase(val); if(l == r) return; int mid = (l + r) >> 1; if(pos <= mid) upd1(id << 1, l, mid, pos, val, add); else upd1(id << 1 | 1, mid + 1, r, pos, val, add); } int get1(int id, int l, int r, int le, int ri){ if(IT1[id].size() == 0) return oo; if(l == r){ int temp = (*IT1[id].begin()); if(temp > ri || temp < le) return oo; return l; } // cout << "ID " << id << " "; // for(auto it : IT1[id]) cout << it << " "; // cout << "\n"; int mid = (l + r) >> 1; if(!IT1[id << 1].size()) return get1(id << 1 | 1, mid + 1, r, le, ri); else{ set<int>::iterator it = IT1[id << 1].lower_bound(le); if(it == IT1[id << 1].end() || (*it) > ri) return get1(id << 1 | 1, mid + 1, r, le, ri); else return get1(id << 1, l, mid, le, ri); } } void upd2(int id, int l, int r, int pos, int val, bool add){ if(add) IT2[id].insert(val); else IT2[id].erase(val); if(l == r) return; int mid = (l + r) >> 1; if(pos <= mid) upd2(id << 1, l, mid, pos, val, add); else upd2(id << 1 | 1, mid + 1, r, pos, val, add); } int get2(int id, int l, int r, int le, int ri){ if(IT2[id].size() == 0) return oo; if(l == r){ int temp = (*IT2[id].begin()); if(temp > ri || temp < le) return oo; return l; } int mid = (l + r) >> 1; if(!IT2[id << 1].size()) return get2(id << 1 | 1, mid + 1, r, le, ri); else{ set<int>::iterator it = IT2[id << 1].lower_bound(le); if(it == IT2[id << 1].end() || (*it) > ri) return get2(id << 1 | 1, mid + 1, r, le, ri); else return get2(id << 1, l, mid, le, ri); } } vector<int> v1, v2; #ifdef local void process(){ cin >> n >> m >> q; for(int i = 1; i <= m; i++){ cin >> x[i] >> y[i]; queries[1].pb(i); } int cnt1 = m, cnt2 = 0, cnt3 = 0; for(int i = 1; i <= q; i++){ int typ; cin >> typ; if(typ == 1){ int x; cin >> x; cnt3++; asks[x].pb({cnt2, cnt3}); } else if(typ == 2){ cnt2++; int l; cin >> l; type[cnt2] = 0, width[cnt2] = l; } else if(typ == 3){ cnt2++; int l; cin >> l; type[cnt2] = 1, width[cnt2] = l; } else{ cnt1++; cin >> x[cnt1] >> y[cnt1]; queries[cnt2 + 1].pb(cnt1); } } for(int i = 1; i <= cnt1; i++) reverse(asks[i].begin(), asks[i].end()); int cnth = 0, cntv = 0; for(int i = 1; i <= cnt2; i++){ if(type[i] == 0) cnth++; else cntv++; } int temph = cnth, tempv = cntv; cnth = 0, cntv = 0; v1.pb(-1), v2.pb(-1); for(int i = 1; i <= cnt2; i++){ if(type[i] == 0){ cnth++; // cout << "OKOKOK " << width[i] << "\n"; upd1(1, 1, temph, cnth, width[i], 1); v1.pb(i); } else{ cntv++; upd2(1, 1, tempv, cntv, width[i], 1); v2.pb(i); } } v1.pb(oo), v2.pb(oo); //return; cnth = 0, cntv = 0; for(int i = 1; i <= cnt2; i++){ for(auto it : queries[i]){ int pos = it, pos1 = oo, pos2 = oo; // H first: given current (x, y) int le = y[pos], ri = n - x[pos] - 1; if(le <= ri) pos1 = get1(1, 1, temph, le, ri); // cout << le << " " << ri << "\n"; le = x[pos], ri = n - y[pos] - 1; if(le <= ri) pos2 = get2(1, 1, tempv, le, ri); // cout << le << " " << ri << "\n"; // continue; pos1 = v1[min((int)v1.size() - 1, pos1)], pos2 = v2[min((int)v2.size() - 1, pos2)]; // cout << i << " " << pos << " " << pos1 << " " << pos2 << "\n"; while(asks[pos].size() && asks[pos].back().fi < min(pos1, pos2)){ // cout << "OK " << asks[pos].back().fi << " " << asks[pos].back().se << "\n"; answer[asks[pos].back().se] = make_pair(x[pos], y[pos]); asks[pos].pop_back(); } if(min(pos1, pos2) > cnt2) continue; // cout << pos1 << " " << pos2 << "\n"; // continue; if(pos1 < pos2) x[pos] = n - width[pos1]; else y[pos] = n - width[pos2]; // cout << pos1 << " " << pos2 << "\n"; // continue; queries[min(pos1, pos2) + 1].pb(it); } if(type[i] == 0){ cnth++; upd1(1, 1, temph, cnth, width[i], 0); } else{ cntv++; upd2(1, 1, temph, cntv, width[i], 0); } } for(int i = 1; i <= cnt1; i++){ for(auto it : asks[i]) answer[it.se] = {x[i], y[i]}; } for(int i = 1; i <= cnt3; i++) cout << answer[i].fi << " " << answer[i].se << "\n"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); process(); } #endif
#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...