#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
pi pos[1500010];
int ng[1500010],gl[1500010],gr[1500010];
struct seg
{
struct node
{
int ind,mid;
vector<vector<int> >vl,vr;
vector<int>lf,rg;
map<int,int>mpl,mpr;
vector<int>nl,nr;
inline int ngl(int l)
{
int g;
if(!nl.empty())
g=nl.back(),nl.pop_back();
else
g=lf.size(),lf.eb(l),vl.eb(vector<int>());
lf[g]=l;
return mpl[l]=g;
}
inline int ngr(int r)
{
int g;
if(!nr.empty())
g=nr.back(),nr.pop_back();
else
g=rg.size(),rg.eb(r),vr.eb(vector<int>());
rg[g]=r;
return mpr[r]=g;
}
inline void dell(int g)
{
vl[g].clear();
vl[g].shrink_to_fit();
nl.eb(g);
return;
}
inline void delr(int g)
{
vr[g].clear();
vr[g].shrink_to_fit();
nr.eb(g);
return;
}
inline void put(int x)
{
ng[x]=ind;
int cl=pos[x].fi;
int cr=pos[x].se;
{
auto it=mpl.find(cl);
if(it==mpl.end())
gl[x]=ngl(cl);
else
gl[x]=it->se;
vl[gl[x]].eb(x);
}
{
auto it=mpr.find(cr);
if(it==mpr.end())
gr[x]=ngr(cr);
else
gr[x]=it->se;
vr[gr[x]].eb(x);
}
return;
}
inline vector<int>pushl(int l)
{
if(l>mid)
{
vector<int>ret;
auto it=mpr.end();
while(it!=mpr.begin())
{
it--;
if(it->fi<l)
break;
int grp=it->se;
for(int&t:vr[grp])
if(ng[t]==ind)
pos[t]=pi(l,rg[grp]),ret.eb(t);
delr(grp);
mpr.erase(it);
it=mpr.end();
}
return ret;
}
vector<int>gv;
auto it=mpl.begin();
int ci=-1,csz=-1;
while(it!=mpl.end())
{
if(it->fi>l)
break;
int grp=it->se;
if((int)vl[grp].size()>csz)
csz=vl[ci=grp].size();
gv.eb(grp);
mpl.erase(it);
it=mpl.begin();
}
if(ci==-1)
return vector<int>();
lf[ci]=l;
mpl[l]=ci;
for(int&t:gv)
{
if(t==ci)
continue;
for(int&x:vl[t])
if(ng[x]==ind)
vl[gl[x]=ci].eb(x);
dell(t);
}
return vector<int>();
}
inline vector<int>pushr(int r)
{
if(r<mid)
{
vector<int>ret;
auto it=mpl.begin();
while(it!=mpl.end())
{
if(it->fi>r)
break;
int grp=it->se;
for(int&t:vl[grp])
if(ng[t]==ind)
pos[t]=pi(lf[grp],r),ret.eb(t);
dell(grp);
mpl.erase(it);
it=mpl.begin();
}
return ret;
}
vector<int>gv;
auto it=mpr.end();
int ci=-1,csz=-1;
while(it!=mpr.begin())
{
it--;
if(it->fi<r)
break;
int grp=it->se;
if((int)vl[grp].size()>csz)
csz=vl[ci=grp].size();
gv.eb(grp);
mpr.erase(it);
it=mpr.end();
}
if(ci==-1)
return vector<int>();
rg[ci]=r;
mpr[r]=ci;
for(int&t:gv)
{
if(t==ci)
continue;
for(int&x:vr[t])
if(ng[x]==ind)
vr[gr[x]=ci].eb(x);
delr(t);
}
return vector<int>();
}
}nd[6000010];
int tree[12000010];
int nct;
inline int nnd(int m)
{
nct++;
nd[nct].ind=nct;
nd[nct].mid=m;
return nct;
}
inline void init(int n,int s,int e)
{
if(s>e)
return;
int m=s+(e-s)/2;
tree[n]=nnd(m);
if(s==e)
return;
init(n*2,s,m-1);
init(n*2+1,m+1,e);
return;
}
void put(int n,int s,int e,int x)
{
int m=s+(e-s)/2;
if(pos[x].se<m)
return put(n*2,s,m-1,x);
if(pos[x].fi>m)
return put(n*2+1,m+1,e,x);
nd[tree[n]].put(x);
return;
}
void pushl(int n,int s,int e,int l)
{
if(l<=s||l>e)
return;
int m=s+(e-s)/2;
vector<int>pv=nd[tree[n]].pushl(l);
for(int&t:pv)
put(n*2+1,m+1,e,t);
pushl(n*2,s,m-1,l);
pushl(n*2+1,m+1,e,l);
return;
}
void pushr(int n,int s,int e,int r)
{
if(r<s||r>=e)
return;
int m=s+(e-s)/2;
vector<int>pv=nd[tree[n]].pushr(r);
for(int&t:pv)
put(n*2,s,m-1,t);
pushr(n*2,s,m-1,r);
pushr(n*2+1,m+1,e,r);
return;
}
inline pi print(int x)
{
return pi(nd[ng[x]].lf[gl[x]],nd[ng[x]].rg[gr[x]]);
}
}st;
int pct;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,q;
cin>>n>>m>>q;
vector<int>cpv;
for(int i=0;i++<m;)
{
cin>>pos[i].fi>>pos[i].se;
pos[i].se=n-pos[i].se;
cpv.eb(pos[i].fi),cpv.eb(pos[i].se);
}
vector<pi>qv;
pct=m;
for(int i=0;i<q;i++)
{
int t,l;
cin>>t>>l;
if(t==2)
cpv.eb(l=n-l);
else if(t==3)
cpv.eb(l);
else if(t==4)
{
pos[++pct].fi=l;
cin>>pos[pct].se;
pos[pct].se=n-pos[pct].se;
cpv.eb(pos[pct].fi),cpv.eb(pos[pct].se);
}
qv.eb(t,l);
}
sort(all(cpv));
cpv.erase(unique(all(cpv)),cpv.end());
for(int i=0;i++<pct;)
pos[i].fi=lower_bound(all(cpv),pos[i].fi)-cpv.begin(),
pos[i].se=lower_bound(all(cpv),pos[i].se)-cpv.begin();
int cn=cpv.size();
st.init(1,0,cn-1);
for(int i=0;i++<m;)
st.put(1,0,cn-1,i);
pct=m;
for(pi&t:qv)
{
if(t.fi==1)
{
pi p=st.print(t.se);
cout<<cpv[p.fi]<<' '<<(n-cpv[p.se])<<'\n';
}
else if(t.fi==2)
st.pushl(1,0,cn-1,(int)(lower_bound(all(cpv),t.se)-cpv.begin()));
else if(t.fi==3)
st.pushr(1,0,cn-1,(int)(lower_bound(all(cpv),t.se)-cpv.begin()));
else
st.put(1,0,cn-1,++pct);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
937 ms |
1457600 KB |
Output is correct |
| 2 |
Incorrect |
939 ms |
1456940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8341 ms |
1736572 KB |
Output is correct |
| 2 |
Correct |
7918 ms |
1754100 KB |
Output is correct |
| 3 |
Correct |
7814 ms |
1753504 KB |
Output is correct |
| 4 |
Correct |
5814 ms |
1689356 KB |
Output is correct |
| 5 |
Correct |
9515 ms |
1866476 KB |
Output is correct |
| 6 |
Correct |
9690 ms |
1811768 KB |
Output is correct |
| 7 |
Correct |
7543 ms |
1744620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4498 ms |
1619596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4498 ms |
1619596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
937 ms |
1457600 KB |
Output is correct |
| 2 |
Incorrect |
939 ms |
1456940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
