제출 #441028

#제출 시각아이디문제언어결과실행 시간메모리
441028RedhoodSegments (IZhO18_segments)C++14
0 / 100
715 ms5272 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 = 2000; const int C = buben*2; int L[N], R[N]; int memory[N]; int oukek[N/buben+1]; vector<int>ID[N/buben+1],X[N/buben+1],Y[N/buben+1],Ylen[N/buben+1]; set < pair < int , int > > have; int numofblock[N], YV[N], YVlen[N]; int done = 0; int blocks=1; void rebuild(){ // cerr << "rebuild start\n"; ///i love this trick, yup for(int x = 0; x < blocks; ++x) ID[x].clear(), X[x].clear(), Y[x].clear(), Ylen[x].clear(); int n = len(have); assert(n >= 1); n = max(n , 1); blocks = (n-1)/buben+1; for(int i = 0; i <= (n-1)/buben; ++i){ oukek[i]=0; if(i < (n-1)/buben){ X[i].resize(buben); ID[i].resize(buben); Y[i].resize(buben); Ylen[i].resize(buben); }else{ int left = n - max(0,((n-1)/buben-1)+1)*buben; X[i].resize(left); ID[i].resize(left); Y[i].resize(left); Ylen[i].resize(left); } } int ind=0; for(auto u : have){ X[ind/buben][ind%buben] = L[u.se]; ID[ind/buben][ind%buben] = u.se; Y[ind/buben][ind%buben] = R[u.se]; Ylen[ind/buben][ind%buben] = R[u.se]-L[u.se]+1; numofblock[u.se] = ind/buben; ind++; } for(int i = 0 ; i <= (n-1)/buben; ++i) sort(all(Y[i])), sort(all(Ylen[i])); } void add(int id, int y, int Len){ int x = L[id]; have.insert({x , id}); YV[id] = y; YVlen[id] = Len; for(int idb = 0; idb < blocks; ++idb){ if(idb == blocks-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); int ps2 = lower_bound(all(Ylen[idb]), Len) - Ylen[idb].begin(); Ylen[idb].insert(Ylen[idb].begin()+ps2, Len); numofblock[id] = idb; break; } } done++; if(done == C){ done = 0; rebuild(); } } void del(int id, int y, int Len){ int x = L[id]; have.erase({x ,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)); Ylen[idb].erase(lower_bound(all(Ylen[idb]), Len)); ID[idb].erase(ID[idb].begin()+i); break; } } assert(found); } int qryR(int Lx, int Rx, int Yl){ if(Lx > Rx) return 0; int ans = 0; for(int idb = 0 ; idb < blocks; ++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; for(int i = 0 ; i < len(X[idb]); ++i){ if(X[idb][i] >= Lx && X[idb][i] <= Rx && YV[ID[idb][i]] >= Yl) ans++; } } } return ans; } int qryLen(int Lx, int Rx, int Yl){ if(Lx > Rx) return 0; int ans = 0; for(int idb = 0 ; idb < blocks; ++idb){ if(X[idb][0] >= Lx && X[idb].back() <= Rx){ ans += Ylen[idb].end() - lower_bound(all(Ylen[idb]), Yl); }else{ if(X[idb][0] > Rx) break; if(X[idb].back() < Lx) continue; for(int i = 0 ; i < len(X[idb]); ++i){ if(X[idb][i] >= Lx && X[idb][i] <= Rx && YVlen[ID[idb][i]] >= Yl) ans++; } } } return ans; } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); 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; add(lst, R[lst], R[lst]-L[lst]+1); lst++; } if(type == 2){ int id;cin >> id; del(id, R[id], R[id]-L[id]+1); } 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 = qryR(a, b-k+1, k) + qryLen(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...