#pragma GCC optimize("Ofast")
#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 time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1368 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4137 ms |
273396 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3423 ms |
225700 KB |
Output is correct |
| 2 |
Correct |
3013 ms |
225480 KB |
Output is correct |
| 3 |
Execution timed out |
18054 ms |
211524 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3423 ms |
225700 KB |
Output is correct |
| 2 |
Correct |
3013 ms |
225480 KB |
Output is correct |
| 3 |
Execution timed out |
18054 ms |
211524 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1368 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
