#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
typedef long long ll;
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (1500006) // change MAXN later
struct Query{
ll t, ind, l, x, y, QI;
};vector<Query> Q;
ll n,m,q,cnt;
pi pos[MAXN],ans[MAXN];
vector<ll> v[MAXN*2];
struct ufds_ {
int p[MAXN*2];
void init(ll x) {
FOR(i,0,x+1) p[i]=i, v[i].clear(), v[i].pb(i);
}
void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(siz(v[x])>siz(v[y]))swap(x,y);
p[x]=y;
for(auto i:v[x]) v[y].pb(i);
v[x].clear();
}
int find(int x) { return (p[x]==x)?x:p[x]=find(p[x]); }
bool same(int x,int y) { return find(x)==find(y); }
} ufds;
void dnc(ll x,ll y,vector<Query> Q){
if(Q.empty())return;
sort(all(Q),[](Query x,Query y){return x.QI<y.QI;});
ll diff=n-x-y;
if(diff == 0) { // do something(?) just answer the Queries(?)
for(auto i:Q) if(i.t==1) ans[i.ind]={x,y};
return;
}
ll X=x+(diff+1)/2, Y=y+diff/2+1, cnt=0, act=0;
ufds.init(Q.size()*2+3);
vector<bool> gone(Q.size(), 0);
vector<Query> UP, RI;
priority_queue<pi,vector<pi>,greater<pi>> px, py;
map<ll,ll> gcnt, cntQ;
vector<ll> xnow(Q.size(),0), ynow(Q.size(),0);
for(auto i:Q) if(i.t==4) { xnow[cnt]=i.x, ynow[cnt]=i.y; gcnt[i.ind]=cnt; cntQ[cnt]=act; ++ cnt, ++ act; } else ++ act;
cnt=0;
for(auto i:Q){
if(i.t==1){// reconsider index pls
Query tmp = i;
i.l=gcnt[i.l];
auto D=[&](ll a,ll b,ll c,ll d){
return c;
};
if(gone[i.l]){
// decide whether to push Query into UP or RI
if(xnow[D(ufds.find(i.l<<1|1),i.l<<1|1,ufds.find(i.l<<1),i.l<<1)>>1] >= X) {
assert(ynow[D(ufds.find(i.l<<1),i.l<<1,ufds.find(i.l<<1|1),i.l<<1|1)>>1] < Y);
RI.pb(tmp);
}else if(ynow[D(ufds.find(i.l<<1),i.l<<1,ufds.find(i.l<<1|1),i.l<<1|1)>>1] >= Y) {
UP.pb(tmp);
}else {
// cerr<<x<<' '<<y<<'\n';
assert(0);
}
}else{
ans[i.ind]=pi(xnow[D(ufds.find(i.l<<1|1),i.l<<1|1,ufds.find(i.l<<1),i.l<<1)>>1],ynow[D(ufds.find(i.l<<1),i.l<<1,ufds.find(i.l<<1|1),i.l<<1|1)>>1]);
}
}else if(i.t==2){ // horizontal
if(n-i.l >= X) { // protrudes
RI.pb(i);
// all y <= i.l, set gone = 1, push RI, rmbr to set xnow, cos queries need to go where to go
while(py.size()) {
if(py.top().f > i.l) break;
ll x=py.top().s;
py.pop();
if(gone[x>>1])continue;
assert(ufds.find(x)==x);
xnow[x>>1]=n-i.l;assert(n-i.l>=X);
auto tmp=i;
for(auto i:v[x]) if(ufds.find(i)==x && !gone[i>>1]) {
xnow[i>>1]=n-tmp.l, gone[i>>1]=1, RI.pb(Q[cntQ[i>>1]]);
}
for(auto i:v[x]) ufds.p[i]=i, v[i].clear(), v[i].pb(i), ufds.p[i-1]=i-1,v[i-1].clear(),v[i-1].pb(i-1);
}
}else {// def taller than square
UP.pb(i);
ll lst=-1;
while(px.size()){
if(px.top().f>n-i.l) break;
ll x=px.top().s;
px.pop();
if(gone[x>>1])continue;
if(~lst){
ufds.merge(lst,x);
}
lst=x;
}
if(~lst) lst=ufds.find(lst), xnow[lst>>1]=n-i.l, px.emplace(xnow[lst>>1],lst);
}
}else if(i.t==3){ // vertical
if(n-i.l>=Y){//protrudes
UP.pb(i);
while(px.size()){
if(px.top().f>i.l)break;
ll x=px.top().s;
px.pop();
if(gone[x>>1])continue;
assert(ufds.find(x)==x);
ynow[x>>1]=n-i.l;assert(n-i.l>=Y);
auto tmp=i;
for(auto i:v[x]) if(ufds.find(i) == x && !gone[i>>1]) {
ynow[i>>1]=n-tmp.l, assert(ufds.find(i)==x), gone[i>>1]=1, UP.pb(Q[cntQ[i>>1]]);
}
for(auto i:v[x]) ufds.p[i]=i, v[i].clear(), v[i].pb(i),ufds.p[i+1]=i+1,v[i+1].clear(),v[i+1].pb(i+1);
}
}else{//def wider than sqaure
RI.pb(i);
ll lst=-1;
while(py.size()){
if(py.top().f>n-i.l)break;
ll x=py.top().s;
py.pop();
if(gone[x>>1])continue;
if(~lst) {
ufds.merge(lst, x);
}
lst=x;
}
if(~lst) lst=ufds.find(lst), ynow[lst>>1]=n-i.l, py.emplace(ynow[lst>>1],lst);
}
}else{ // add new point
if(i.x >= X) { assert(i.y < Y);
gone[cnt]=1, RI.pb(i);
}else if(i.y >= Y) { assert(i.x < X);
gone[cnt]=1, UP.pb(i);
}else{
px.emplace(i.x, cnt<<1);
py.emplace(i.y, cnt<<1|1);
}
++ cnt;
}
} // cannot change the array pos at the end, as in separate dncs, some moves might end up coming first
// cerr<<X<<' '<<y<<" RI: ";
// for(auto i:RI) cerr<<i.QI<<' ';
// cerr<<'\n';
// cerr<<x<<' '<<Y<<" UP: ";
// for(auto i:UP) cerr<<i.QI<<' ';
// cerr<<'\n';
dnc(X,y,RI);
dnc(x,Y,UP);
}
int main(){
FAST
cin>>n>>m>>q;
FOR(i,1,m){
++ cnt;
cin>>pos[cnt].f>>pos[cnt].s;
Q.pb({4,cnt,-1,pos[cnt].f,pos[cnt].s});
}
FOR(ii,1,q){
ll t;cin>>t;
if(t<=3){
ll l;cin>>l;
Q.pb({t,ii,l,-1,-1});
}else{
++ cnt;
cin>>pos[cnt].f>>pos[cnt].s;
Q.pb({4,cnt,-1,pos[cnt].f,pos[cnt].s});
}
}
FOR(i,0,siz(Q)-1)Q[i].QI=i;
mmst(ans,-1);
dnc(0,0,Q);
FOR(i,1,q)if(ans[i]!=pi(-1,-1))cout<<ans[i].f<<' '<<ans[i].s<<'\n';
}
/*
20 1 7
1 0
2 18
3 9
3 10
3 3
2 9
3 12
1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
98292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12197 ms |
803420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12384 ms |
998748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12384 ms |
998748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
98292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
