Submission #1003640

#TimeUsernameProblemLanguageResultExecution timeMemory
1003640UnforgettableplSweeping (JOI20_sweeping)C++17
0 / 100
18109 ms283324 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define int long long typedef tree<pair<int,int>,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> orderedset; struct triangle{ mutable orderedset x,y; triangle(){} bool operator<(const triangle& other) const {return false;} }; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n,m,q; cin >> n >> m >> q; vector<int const*> pos(m+1); vector<pair<int,int>> defaultpos(m+1); set<pair<int,triangle>> room; set<int> points = {0,n}; room.insert({n,{}}); for(int i=1;i<=m;i++){ int x,y;cin>>x>>y; defaultpos[i]={x,y}; room.begin()->second.x.insert({x,i}); room.begin()->second.y.insert({y,i}); pos[i] = &(room.begin()->first); } for(int i=1;i<=q;i++){ int type;cin>>type; if(type==1){ int x;cin>>x; // CALCULATE POSITION OF DUST x int curr = 0,before=0; if(pos[x]!=nullptr){ curr = *pos[x]; before = *--points.lower_bound(curr); curr = n-curr; } cout << max(defaultpos[x].first,curr) << ' ' << max(defaultpos[x].second,before) << '\n'; } else if(type==2){ int l;cin>>l; auto curr = room.extract(room.lower_bound({l,{}})); if(l==curr.value().first){ room.insert(move(curr)); curr = room.extract(room.upper_bound({l,{}})); while(curr.value().second.y.size() and (*curr.value().second.y.begin()).first<=l){ auto idx = (*curr.value().second.y.begin()).second; defaultpos[idx] = {n-l,l}; pos[idx] = nullptr; curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx))); curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx))); } room.insert(move(curr)); continue; } if(2*curr.value().second.y.order_of_key({l,0})>curr.value().second.y.size()){ // Modify current one auto newer = triangle(); vector<int> buffer; while(curr.value().second.y.size() and (*--curr.value().second.y.end()).first>l){ auto idx = (*--curr.value().second.y.end()).second; newer.x.insert(make_pair(defaultpos[idx].first,idx)); newer.y.insert(make_pair(defaultpos[idx].second,idx)); curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx))); curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx))); buffer.emplace_back(idx); } auto ptr = &(room.insert({curr.value().first,newer}).first->first); for(int&x:buffer)pos[x]=ptr; curr.value().first = l; room.insert(move(curr)); } else { // Modify new one auto newer = triangle(); vector<int> buffer; while(curr.value().second.y.size() and (*curr.value().second.y.begin()).first<=l){ auto idx = (*curr.value().second.y.begin()).second; newer.x.insert(make_pair(defaultpos[idx].first,idx)); newer.y.insert(make_pair(defaultpos[idx].second,idx)); curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx))); curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx))); buffer.emplace_back(idx); } auto ptr = &(room.insert({l,newer}).first->first); for(int&x:buffer)pos[x]=ptr; room.insert(move(curr)); } points.insert(l); } else if(type==3){ int l;cin>>l;int lx = n-l; auto curr = room.extract(room.lower_bound({lx,{}})); if(lx==curr.value().first){ while(curr.value().second.x.size() and (*curr.value().second.x.begin()).first<=l){ auto idx = (*curr.value().second.x.begin()).second; defaultpos[idx]={l,lx}; pos[idx]=nullptr; curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx))); curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx))); } room.insert(move(curr)); continue; } if(2*curr.value().second.x.order_of_key({l,0})>curr.value().second.x.size()){ // Modify newer one auto newer = triangle(); vector<int> buffer; while(curr.value().second.x.size() and (*--curr.value().second.x.end()).first>l){ auto idx = (*--curr.value().second.x.end()).second; newer.x.insert(make_pair(defaultpos[idx].first,idx)); newer.y.insert(make_pair(defaultpos[idx].second,idx)); curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx))); curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx))); buffer.emplace_back(idx); } auto ptr = &(room.insert({lx,newer}).first->first); for(int&x:buffer)pos[x]=ptr; room.insert(move(curr)); } else { // Modify current one auto newer = triangle(); vector<int> buffer; while(curr.value().second.x.size() and (*curr.value().second.x.begin()).first<=l){ auto idx = (*curr.value().second.x.begin()).second; newer.x.insert(make_pair(defaultpos[idx].first,idx)); newer.y.insert(make_pair(defaultpos[idx].second,idx)); curr.value().second.x.erase(curr.value().second.x.find(make_pair(defaultpos[idx].first,idx))); curr.value().second.y.erase(curr.value().second.y.find(make_pair(defaultpos[idx].second,idx))); buffer.emplace_back(idx); } auto ptr = &(room.insert({curr.value().first,newer}).first->first); for(int&x:buffer)pos[x]=ptr; curr.value().first = lx; room.insert(move(curr)); } points.insert(lx); } } }
#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...