제출 #260133

#제출 시각아이디문제언어결과실행 시간메모리
260133shayan_p청소 (JOI20_sweeping)C++14
100 / 100
7214 ms367644 KiB
// And you curse yourself for things you never done #include<bits/stdc++.h> #define F first #define S second #define PB push_back #define sz(s) int((s).size()) #define bit(n,k) (((n)>>(k))&1) using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<pii, pii> pi4; const int maxn = 2e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10; int N; pii trans(pii p){ // x1 x2 return {p.S, N - p.F}; } pii trans2(pii p){ // x1 x2 return {p.F, N - p.S}; } struct bigTraingle{ map<pii, pii> mp; vector<pair<pii, int> > v; int sp[21][maxn]; void restart(){ mp.clear(); mp[{0, N}] = {0, 0}; } pii color(pii p){ int L = upper_bound(v.begin(), v.end(), (pair<pii, int>){{p.F, inf}, inf}) - v.begin() - 1; int R = upper_bound(v.begin(), v.end(), (pair<pii, int>){{N - p.S, inf}, inf}) - v.begin(); assert(L < R); int lg = 31 - __builtin_clz(R-L); int A = sp[lg][L], B = sp[lg][R - (1<<lg)]; if(v[B].S < v[A].S) A = B; return v[A].F; } void add(int l, bool is){ int x = l, y = N - l; if(is) swap(x, y); auto it = --mp.upper_bound({x, inf}); int L = it->F.F, R = it->F.S; pii p = it->S; mp.erase(it); if(!is){ pii A = {L, x}, B = {x + 1, R}; mp[A] = p; if(B.F <= B.S) mp[B] = {B.F, p.S}; } else{ pii A = {L, x - 1}, B = {x, R}; mp[B] = p; if(A.F <= A.S) mp[A] = {p.F, N - A.S}; } } pii calc(pii p){ pii s = color(p); pii C = trans2(s); return {max(C.F, p.F), max(C.S, p.S)}; } void prepare(){ v.clear(); for(auto x : mp){ v.PB({x.F, x.S.F + x.S.S}); } assert(sz(v)); int Log = 31 - __builtin_clz(sz(v)); for(int i = 0; i < sz(v); i++) sp[0][i] = i; for(int i = 1; i <= Log; i++){ for(int j = 0; j < sz(v); j++){ sp[i][j] = sp[i-1][j]; int k = j + (1<<(i-1)); if(k < sz(v) && v[sp[i-1][j]].S > v[sp[i-1][k]].S) sp[i][j] = sp[i-1][k]; } } } }; int prog[maxn]; //////to Del int LST[maxn]; vector<pii> conf, p, tell[maxn]; pii ans[maxn]; vector<int> tdo[4 * maxn]; void place(int f, int s, int x, int l = 0, int r = sz(conf) + 1, int id = 1){ if(f >= s || s <= l || r <= f) return; if(f <= l && r <= s){ tdo[id].PB(x); return; } int mid = (l+r) >> 1; place(f, s, x, l, mid, 2*id); place(f, s, x, mid, r, 2*id+1); } bigTraingle tr; void solve(int l = 0, int r = sz(conf) + 1, int id = 1){ if(r-l == 1){ for(pii x : tell[l]){ assert(prog[x.F] == l); ans[x.S] = p[x.F]; } } if(r-l > 1){ int mid = (l+r) >> 1; solve(l, mid, 2*id); solve(mid, r, 2*id + 1); } if(r == sz(conf) + 1) assert(tdo[id].empty()); if(tdo[id].empty()) return; tr.restart(); for(int i = l; i < r; i++) tr.add(conf[i].F, conf[i].S); tr.prepare(); for(int i : tdo[id]){ assert(prog[i] == l); prog[i] = r; p[i] = tr.calc(p[i]); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(); int m, q; cin >> N >> m >> q; p.resize(m); for(int i = 0; i < m; i++){ cin >> p[i].F >> p[i].S; } vector<pair<pii, int> > seg; int Q = 0; for(int i = 0; i < q; i++){ int task; cin >> task; if(task == 1){ int id; cin >> id; --id; tell[sz(conf)].PB({id, Q++}); seg.PB({{LST[id], sz(conf)}, id}); LST[id] = sz(conf); } if(task == 2){ int l; cin >> l; conf.PB({l, 1}); } if(task == 3){ int l; cin >> l; conf.PB({l, 0}); } if(task == 4){ int x, y; cin >> x >> y; LST[sz(p)] = sz(conf); prog[sz(p)] = sz(conf); p.PB({x, y}); } } for(auto x : seg){ place(x.F.F, x.F.S, x.S); } solve(); for(int i = 0; i < Q; i++){ cout << ans[i].F << " " << ans[i].S << "\n"; } 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...