#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef unsigned long long ull;
typedef long double ld;
#define fr first
#define sc second
#define pb push_back
#define INF 1000000007
#define N 100000
#define endl '\n'
ll n,m,q,h,X,Y;
struct D{
ll u,r,x,y,s[2],gx,gy;
}l;
struct T{
ll x,y,r,s[2],num,u[2],numdek;
}t[1500007];
struct Tree{
ll l,r,prom,key,mx,h,par,num;
}tre;
vector<D>d;
vector<vector<ll> >v[2];
vector<vector<Tree> >tr[2];
set<pairlll>k,k1,ps;
vector<ll>v1,root[2],sz[2],widlozhene;
set<ll>u1;
vector<Tree> tree;
void AddF(ll r,ll x,ll y,ll tp){
for(int i=x;i>0;i-=(i&-i)){
v[tp][r][i]=max(v[tp][r][i],y);
}
return ;
}
ll R(ll r,ll tp,ll x){
ll res=0;
for(int i=x;i<v[tp][r].size();i+=(i&-i)){
res=max(res,v[tp][r][i]);
}
return res;
}
void Push(ll x,ll y,ll tp,ll r){
if(x==-1)return ;
tr[tp][r][x].h=y;
tr[tp][r][x].prom=y;
tr[tp][r][x].mx=y;
return ;
}
pairll S(ll x,ll y,ll tp,ll r){
if(x==-1)return {-1,-1};
if(tr[tp][r][x].prom!=0){
Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
tr[tp][r][x].prom=0;
}
tr[tp][r][x].par=-1;
if(tr[tp][r][x].h<=y){
pairll m1=S(tr[tp][r][x].r,y,tp,r);
tr[tp][r][x].r=m1.fr;
if(tr[tp][r][x].r!=-1){
tr[tp][r][x].mx=max(tr[tp][r][x].h,tr[tp][r][tr[tp][r][x].r].mx);
tr[tp][r][tr[tp][r][x].r].par=x;
}else{
tr[tp][r][x].mx=tr[tp][r][x].h;
}
return {x,m1.sc};
}else{
pairll m1=S(tr[tp][r][x].l,y,tp,r);
tr[tp][r][x].l=m1.sc;
if(tr[tp][r][x].l!=-1){
tr[tp][r][tr[tp][r][x].l].par=x;
}
return {m1.fr,x};
}
}
ll M(ll x,ll y,ll tp,ll r){
if(x==-1)return y;
if(y==-1)return x;
tr[tp][r][x].par=-1;
tr[tp][r][y].par=-1;
if(tr[tp][r][x].prom!=0){
Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
tr[tp][r][x].prom=0;
}
if(tr[tp][r][y].prom!=0){
Push(tr[tp][r][y].l,tr[tp][r][y].prom,tp,r);
Push(tr[tp][r][y].r,tr[tp][r][y].prom,tp,r);
tr[tp][r][y].prom=0;
}
if(tr[tp][r][x].key>tr[tp][r][y].key){
tr[tp][r][x].r=M(tr[tp][r][x].r,y,tp,r);
if(tr[tp][r][x].r!=-1){
tr[tp][r][x].mx=max(tr[tp][r][x].h,tr[tp][r][tr[tp][r][x].r].mx);
tr[tp][r][tr[tp][r][x].r].par=x;
}else{
tr[tp][r][x].mx=tr[tp][r][x].h;
}
return x;
}else{
tr[tp][r][y].l=M(x,tr[tp][r][y].l,tp,r);
if(tr[tp][r][y].l!=-1){
tr[tp][r][tr[tp][r][y].l].par=y;
}
return y;
}
}
void Adddek(ll x,ll r,ll tp,ll num){
pairll m1=S(root[tp][r],x,tp,r);
t[num].numdek=sz[tp][r];
tr[tp][r].pb(tre);
tr[tp][r][sz[tp][r]].l=-1;
tr[tp][r][sz[tp][r]].r=-1;
tr[tp][r][sz[tp][r]].key=rand();
tr[tp][r][sz[tp][r]].mx=x;
tr[tp][r][sz[tp][r]].h=x;
tr[tp][r][sz[tp][r]].par=-1;
tr[tp][r][sz[tp][r]].num=num;
root[tp][r]=M(M(m1.fr,sz[tp][r],tp,r),m1.sc,tp,r);
sz[tp][r]++;
return ;
}
ll Deldek(ll x,ll vnum,ll tp,ll r){
if(x==-1)return -1;
if(vnum+1==widlozhene.size()){
tr[tp][r][x].par=-1;
if(tr[tp][r][x].prom!=0){
Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
tr[tp][r][x].prom=0;
}
return M(tr[tp][r][x].l,tr[tp][r][x].r,tp,r);
}
tr[tp][r][x].par=-1;
if(tr[tp][r][x].prom!=0){
Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
tr[tp][r][x].prom=0;
}
if(widlozhene[vnum+1]==tr[tp][r][x].l){
tr[tp][r][x].l=Deldek(tr[tp][r][x].l,vnum+1,tp,r);
if(tr[tp][r][x].l!=-1){
tr[tp][r][tr[tp][r][x].l].par=x;
}
}else{
tr[tp][r][x].r=Deldek(tr[tp][r][x].r,vnum+1,tp,r);
if(tr[tp][r][x].r!=-1){
tr[tp][r][x].mx=max(tr[tp][r][x].h,tr[tp][r][tr[tp][r][x].r].mx);
tr[tp][r][tr[tp][r][x].r].par=x;
}else{
tr[tp][r][x].mx=tr[tp][r][x].h;
}
}
return x;
}
void Del(ll x,ll tp,ll r){
while(x!=-1){
widlozhene.pb(x);
x=tr[tp][r][x].par;
}
reverse(widlozhene.begin(),widlozhene.end());
root[tp][r]=Deldek(root[tp][r],0,tp,r);
widlozhene.clear();
return ;
}
void Update(ll x,ll y,ll tp,ll r){
if(x==-1)return ;
if(tr[tp][r][x].mx<=y){
tr[tp][r][x].mx=y;
tr[tp][r][x].h=y;
tr[tp][r][x].prom=y;
return ;
}
if(tr[tp][r][x].prom!=0){
Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
tr[tp][r][x].prom=0;
}
Update(tr[tp][r][x].l,y,tp,r);
if(tr[tp][r][x].h<y){
tr[tp][r][x].h=y;
tr[tp][r][x].mx=max(y,tr[tp][r][x].mx);
Update(tr[tp][r][x].r,y,tp,r);
}
return ;
}
void Add(ll x,ll y,ll num,ll r);
void Perekinuvy(ll x,ll y,ll tp,ll r){
if(x==-1)return ;
if(tr[tp][r][x].prom!=0){
Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
tr[tp][r][x].prom=0;
}
ll z=tr[tp][r][x].num;
t[z].x=max(t[z].x,tr[tp][r][x].h);
t[z].y=max(t[z].y,y);
Perekinuvy(tr[tp][r][x].l,y,tp,r);
Perekinuvy(tr[tp][r][x].r,y,tp,r);
Del(t[z].numdek,1,t[z].r);
Add(t[z].x,t[z].y,z,t[z].r);
return ;
}
void Perekinuvx(ll x,ll y,ll tp,ll r){
if(x==-1)return ;
if(tr[tp][r][x].prom!=0){
Push(tr[tp][r][x].l,tr[tp][r][x].prom,tp,r);
Push(tr[tp][r][x].r,tr[tp][r][x].prom,tp,r);
tr[tp][r][x].prom=0;
}
ll z=tr[tp][r][x].num;
t[z].y=max(t[z].y,tr[tp][r][x].h);
t[z].x=max(t[z].x,y);
if(t[z].y>Y)exit(1);
Perekinuvx(tr[tp][r][x].l,y,tp,r);
Perekinuvx(tr[tp][r][x].r,y,tp,r);
Del(t[z].numdek,0,t[z].r);
Add(t[z].x,t[z].y,z,t[z].r);
return ;
}
void Newy(ll r){
if(d[r].u==-1){
h++;
d.pb(l);
v[0].pb(v1);
v[1].pb(v1);
v[0][h].pb(0);
v[1][h].pb(0);
d[r].u=h;
d[h].u=-1;
d[h].r=-1;
d[h].x=(d[r].x+d[r].gx)/2;
d[h].y=n-d[h].x;
d[h].gx=d[r].gx;
d[h].gy=d[r].y;
d[h].s[0]=1;
d[h].s[1]=1;
tr[0].pb(tree);
tr[1].pb(tree);
root[0].pb(-1);
root[1].pb(-1);
sz[0].pb(0);
sz[1].pb(0);
}
return ;
}
void Newx(ll r){
if(d[r].r==-1){
h++;
d.pb(l);
v[0].pb(v1);
v[1].pb(v1);
v[0][h].pb(0);
v[1][h].pb(0);
d[r].r=h;
d[h].r=-1;
d[h].u=-1;
d[h].y=(d[r].y+d[r].gy)/2;
d[h].x=n-d[h].y;
d[h].gy=d[r].gy;
d[h].gx=d[r].x;
d[h].s[0]=1;
d[h].s[1]=1;
tr[0].pb(tree);
tr[1].pb(tree);
root[0].pb(-1);
root[1].pb(-1);
sz[0].pb(0);
sz[1].pb(0);
}
return ;
}
void Add(ll x,ll y,ll num,ll r){
while(d[r].x<x || d[r].y<y){
if(x+y>n)exit(0);
if(d[r].y<y){
Newy(r);
r=d[r].u;
}else{
Newx(r);
r=d[r].r;
}
}
t[num].s[0]=d[r].s[0];
t[num].s[1]=d[r].s[1];
t[num].r=r;
Adddek(x,r,0,num);
Adddek(y,r,1,num);
return ;
}
void Addy(ll x,ll y){
ll r=0;
while(d[r].x<x || d[r].y<y){
if(d[r].y<y){
ll mx=0;
pairll m1=S(root[0][r],x,0,r);
root[0][r]=m1.sc;
Perekinuvy(m1.fr,y,0,r);
Newy(r);
r=d[r].u;
}else{
Update(root[1][r],y,1,r);
v[1][r].pb(0);
AddF(r,d[r].s[1],y,1);
d[r].s[1]++;
Newx(r);
r=d[r].r;
}
}
Update(root[1][r],y,1,r);
v[1][r].pb(0);
AddF(r,d[r].s[1],y,1);
d[r].s[1]++;
return ;
}
///////
void Addx(ll x,ll y){
ll r=0;
while(d[r].x<x || d[r].y<y){
if(d[r].x<x){
ll mx=0;
pairll m1=S(root[1][r],y,1,r);
root[1][r]=m1.sc;
Perekinuvx(m1.fr,x,1,r);
Newx(r);
r=d[r].r;
}else{
Update(root[0][r],x,0,r);
v[0][r].pb(0);
AddF(r,d[r].s[0],x,0);
d[r].s[0]++;
Newy(r);
r=d[r].u;
}
}
Update(root[0][r],x,0,r);
v[0][r].pb(0);
AddF(r,d[r].s[0],x,0);
d[r].s[0]++;
return ;
}
int main()
{
cin>>n>>m>>q;
d.pb(l);
v[0].pb(v1);
v[1].pb(v1);
v[0][0].pb(0);
v[1][0].pb(0);
d[0].u=-1;
d[0].r=-1;
d[0].y=n/2;
d[0].x=n-d[0].y;
d[0].s[0]=1;
d[0].s[1]=1;
tr[0].pb(tree);
tr[1].pb(tree);
root[0].pb(-1);
root[1].pb(-1);
sz[0].pb(0);
sz[1].pb(0);
for(int i=1;i<=m;i++){
cin>>t[i].x>>t[i].y;
swap(t[i].x,t[i].y);
t[i].num=i;
Add(t[i].x,t[i].y,i,0);
}
for(int i=1;i<=q;i++){
ll t1;
cin>>t1;
if(t1==4){
m++;
cin>>t[m].x>>t[m].y;
swap(t[m].x,t[m].y);
t[m].num=m;
Add(t[m].x,t[m].y,m,0);
}else if(t1==3){
ll x;
cin>>x;
X=n-x;
Y=x;
Addx(n-x,x);
}else if(t1==2){
ll x;
cin>>x;
X=x;
Y=n-x;
Addy(x,n-x);
}else{
ll x;
cin>>x;
t[x].y=max(t[x].y,R(t[x].r,1,t[x].s[1]));
t[x].x=max(t[x].x,R(t[x].r,0,t[x].s[0]));
Del(t[x].numdek,0,t[x].r);
Del(t[x].numdek,1,t[x].r);
cout<<t[x].y<<" "<<t[x].x<<endl;
Add(t[x].x,t[x].y,x,t[x].r);
}
}
return 0;
}
Compilation message
sweeping.cpp: In function 'll R(ll, ll, ll)':
sweeping.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i=x;i<v[tp][r].size();i+=(i&-i)){
| ~^~~~~~~~~~~~~~~~
sweeping.cpp: In function 'll Deldek(ll, ll, ll, ll)':
sweeping.cpp:151:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | if(vnum+1==widlozhene.size()){
| ~~~~~~^~~~~~~~~~~~~~~~~~~
sweeping.cpp: In function 'void Addy(ll, ll)':
sweeping.cpp:335:16: warning: unused variable 'mx' [-Wunused-variable]
335 | ll mx=0;
| ^~
sweeping.cpp: In function 'void Addx(ll, ll)':
sweeping.cpp:363:16: warning: unused variable 'mx' [-Wunused-variable]
363 | ll mx=0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
6252 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
980 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7878 ms |
1345976 KB |
Output is correct |
| 2 |
Correct |
8457 ms |
1319908 KB |
Output is correct |
| 3 |
Correct |
8068 ms |
1320068 KB |
Output is correct |
| 4 |
Correct |
8655 ms |
984796 KB |
Output is correct |
| 5 |
Correct |
13181 ms |
1325304 KB |
Output is correct |
| 6 |
Correct |
10246 ms |
1245228 KB |
Output is correct |
| 7 |
Correct |
7647 ms |
1262732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
961 ms |
76512 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
961 ms |
76512 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
6252 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
980 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
