제출 #441011

#제출 시각아이디문제언어결과실행 시간메모리
441011RedhoodSegments (IZhO18_segments)C++14
0 / 100
541 ms26652 KiB
#include<bits/stdc++.h> #define fi first #define se second #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define pb push_back #define len(x) (int)(x).size() using namespace std; /// x,y const int N = (int)2e5 + 10; const int buben = 1800; int L[N], R[N]; struct sofuckinsmart{ vector<vector<int>>ID,X,Y; set<pair<int,int>>Xid,Yid; int memory[N], numofblock[N], YV[N]; int done = 0; sofuckinsmart(){ X.pb({}); ID.pb({}); Y.pb({}); } void rebuild(){ cerr << "rebuild start\n"; ///i love this trick, yup ID.clear(); X.clear(); Y.clear(); int n = len(Xid); n = max(n , 1); ID.resize((n-1)/buben + 1); X.resize((n-1)/buben + 1); Y.resize((n-1)/buben + 1); for(int i = 0; i <= (n-1)/buben; ++i){ if(i < (n-1)/buben){ X[i].resize(buben); ID[i].resize(buben); }else{ int left = n - max(0,((n-1)/buben-1))*buben; X[i].resize(left); ID[i].resize(left); } } int ind=0; for(auto u : Xid){ memory[u.se] = ind; ind++; } for(auto u : Yid){ int idb = memory[u.se]/buben, ps = memory[u.se]%buben; ID[idb][ps] = u.se; X[idb][ps] = L[u.se]; Y[idb].pb(u.fi); numofblock[u.se]=idb; } // for(int i = 0 ; i <= (n-1)/buben; ++i) // sort(all(Y[i])), sort(all(X[i])); cerr << "rebuild done\n"; } void add(int id, int y){ int x = L[id]; Xid.insert({x , id}); Yid.insert({y , id}); YV[id] = y; for(int idb = 0; idb < len(Y); ++idb){ if(idb == len(X)-1 || X[idb+1][0] >= x){ int pos = lower_bound(all(X[idb]), x) - X[idb].begin(); X[idb].insert(X[idb].begin()+pos, x); ID[idb].insert(ID[idb].begin()+pos, id); int ps1 = lower_bound(all(Y[idb]), y) - Y[idb].begin(); Y[idb].insert(Y[idb].begin()+ps1, y); numofblock[id] = idb; break; } } done++; if(done == buben){ done = 0; rebuild(); } } void del(int id, int y){ int x = L[id]; Xid.erase({x , id}); Yid.erase({y , id}); int idb = numofblock[id]; bool found=0; for(int i=0;i<len(ID[idb]);++i){ if(ID[idb][i] == id){ found=1; X[idb].erase(lower_bound(all(X[idb]),x)); Y[idb].erase(lower_bound(all(Y[idb]),y)); ID[idb].erase(ID[idb].begin()+i); break; } } assert(found); } int qry(int Lx, int Rx, int Yl){ if(Lx > Rx) return 0; int ans = 0; for(int idb = 0 ; idb < len(X); ++idb){ if(X[idb][0] >= Lx && X[idb].back() <= Rx){ ans += Y[idb].end() - lower_bound(all(Y[idb]), Yl); }else{ if(X[idb][0] > Rx) break; if(X[idb].back() < Lx) continue; if(X[idb][0] >= Lx){ for(int i = 0 ; i < len(X[idb]); ++i){ if(X[idb][i] > Rx) break; if(YV[ID[idb][i]] >= Yl) ans++; } }else{ assert(X[idb].back() >= Lx && X[idb].back() <= Rx); for(int i = len(X[idb])-1 ; i >= 0; --i){ if(X[idb][i] < Lx) break; if(YV[ID[idb][i]] >= Yl) ans++; } } } } return ans; } }Slen, Sr; signed main(){ int n, t; cin >> n >> t; int lst = 1; int lastans = 0; for(int i = 0 ; i < n; ++i){ int type;cin >> type; if(type == 1){ int a,b;cin >> a >> b; a = a ^ (t * lastans); b = b ^ (t * lastans); if(a > b)swap(a , b); L[lst] = a, R[lst] = b; Slen.add(lst, R[lst]-L[lst]+1); Sr.add(lst , R[lst]); lst++; } if(type == 2){ int id;cin >> id; Slen.del(id, R[id]-L[id]+1); Sr.del(id, R[id]); } if(type == 3){ int a,b,k;cin >> a >> b >> k; a = a ^ (t * lastans); b = b ^ (t * lastans); if(a > b)swap(a,b); int answer = Slen.qry(a, b-k+1, k) + Sr.qry(0, a-1, a+k-1); cout << answer << '\n'; lastans = answer; } } return 0; } /* 6 1 1 1 2 3 2 4 2 1 3 5 3 2 3 1 2 1 3 0 3 1 6 0 1 3 10 1 3 5 3 6 10 6 2 1 1 3 10 3 6 4 2 */
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...