#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll INF = 1e18;
const ll MAXN = 1.5e6+100;
struct query{
ll t,p,x,y;
};
pll ans[MAXN];
ll val[MAXN*2];
ll dsu[MAXN*2];
ll side[MAXN*2];
vector <ll> comp[MAXN*2];
ll n,m,q;
ll join(ll x,ll y){
if (sz(comp[x]) < sz(comp[y]))swap(x,y);
for (auto z:comp[y]){comp[x].push_back(z);dsu[z] = x;}
return x;
}
void dnc(ll l,ll r,vector <query> all){
ll mid = (l + r) >> 1;
vector <query> L,R;
for (auto x:all){
if (x.t == 4){
dsu[x.p<<1] = x.p<<1;
dsu[x.p<<1|1] = x.p<<1|1;
comp[x.p<<1] = {x.p<<1};
comp[x.p<<1|1] = {x.p<<1|1};
val[x.p<<1] = x.x;
val[x.p<<1|1] = x.y;
side[x.p] = 0;
}
}
if (l==r){
for (auto [t,p,x,y]:all){
if (t==1){
ans[x] = MP(val[p<<1],val[p<<1|1]);
}
}
return;
}
priority_queue <pll,vector <pll>, greater <> > px,py;
for (auto cur:all){
auto [t,p,x,y] = cur;
if (t==1){
if (side[p] == 0){
// cout<<l<<' '<<r<<' '<<x<<' '<<p<<endl;
ans[x] = MP(val[dsu[p<<1]],val[dsu[p<<1|1]]);
}
else if (side[p] == 1)L.push_back(cur);
else if (side[p] == 2){R.push_back(cur);}
}
if (t==2){
if (n-x>=mid+1){
R.push_back(cur);
while (!py.empty() && py.top().fi <= x){
ll u = py.top().se;
py.pop();
for (auto z:comp[u]){
if (side[z>>1]==0){
side[z>>1] = 2;
val[z] = val[u];
val[z^1] = n-x;
z = z>>1;
// if (z==2)cout<<"SUS "<<l<<' '<<r<<' '<<side[z]<<' '<<val[z<<1]<<' '<<val[z<<1|1]<<'\n';
R.push_back({4,z,val[z<<1],val[z<<1|1]});
}
}
}
}
else{
ll r = 0;
while (!px.empty() && px.top().fi <= n-x){
ll u = px.top().se;
px.pop();
r = r?join(r,u):u;
}
if (r){
val[r] = n-x;
px.push(MP(val[r],r));
}
L.push_back(cur);
}
}
if (t==3){
if (x <= mid){
L.push_back(cur);
while (!px.empty() && px.top().fi <= x){
ll u = px.top().se;
px.pop();
for (auto z:comp[u]){
if (side[z>>1]==0){
side[z>>1] = 1;
val[z] = val[u];
val[z^1] = n-x;
z=z>>1;
L.push_back({4,z,val[z<<1],val[z<<1|1]});
}
}
}
}
else{
ll r = 0;
while (!py.empty() && py.top().fi <= n-x){
ll u = py.top().se;
py.pop();
r = r?join(r,u):u;
}
if (r){
val[r] = n-x;
py.push(MP(val[r],r));
}
R.push_back(cur);
}
}
if (t==4){
if (x >= mid + 1){
R.push_back(cur);
side[p] = 2;
}
else if (y >= n-mid){
L.push_back(cur);
side[p] = 1;
}
else{
px.push(MP(val[p<<1],p<<1));
py.push(MP(val[p<<1|1],p<<1|1));
}
}
}
assert(sz(L) + sz(R) <= sz(all));
dnc(l,mid,L);
dnc(mid+1,r,R);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(nullptr);
cin>>n>>m>>q;
vector <query> all;
ll ptr = 0;
for (ll i = 1;i <= m;i ++){
ll x,y;
cin>>x>>y;
all.push_back({4,++ptr,x,y});
}
ll cnt=0;
for (ll i = 1;i <= q;i ++){
ll t;
cin>>t;
if (t==1){
ll p;
cin>>p;
all.push_back({1,p,++cnt,-1});
}
if (t==2){
ll x;
cin>>x;
all.push_back({2,-1,x,-1});
}
if (t==3){
ll x;
cin>>x;
all.push_back({3,-1,x,-1});
}
if (t==4){
ll x,y;
cin>>x>>y;
all.push_back({4,++ptr,x,y});
}
}
dnc(0,n,all);
for (ll i = 1;i <= cnt;i ++)cout<<ans[i].fi<<' '<<ans[i].se<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12832 ms |
80216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15217 ms |
447388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14607 ms |
515832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14607 ms |
515832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12832 ms |
80216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
