제출 #211783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211783		zscoder	청소 (JOI20_sweeping)	C++17	100 / 100	4813 ms	350216 KiB

sweeping

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<ii> pt;

struct query
{
	int ty,val,id;
	query(int _ty=0,int _val=0,int _id=0): ty(_ty),val(_val),id(_id){}
};

int par[3333333];

struct DSU
{
	vi val;
	vector<vi> pset;
	void init()
	{
		val.clear(); pset.clear();
	}
	int add(int v, int id) //v = coordinate, id = id of point
	{
		int newid = val.size();
		val.pb(v); pset.pb({});
		if(id>=0)
		{
			par[id]=newid; //change the parent x or y of the point
			pset[newid].pb(id);
		}
		return newid;
	}
	int merge(int x, int y)
	{
		if(x==y) return x;
		if(pset[x].size()<pset[y].size()) swap(x,y);
		val[x]=max(val[x],val[y]);
		for(int z:pset[y]) 
		{
			par[z]=x; pset[x].pb(z);
		}
		return x;
	}
};

vector<query> queries;
ii ans[1111111];
int n,m,q;
DSU dsu;

ii getcoord(int id) //get coordinates of the point id
{
	//cerr<<id<<' '<<dsu.val.size()<<' '<<par[id*2]<<' '<<par[id*2+1]<<'\n';
	return {dsu.val[par[id*2]],dsu.val[par[id*2+1]]};
}

bool pushed[2222222];

void solve(int x, int y, vector<query> Q)
{
	if(Q.empty()) return ;
	/*
	cerr<<"SOLVE "<<x<<' '<<y<<'\n';
	cerr<<"QUERIES: \n";
	for(query qq:Q)
	{
		cerr<<qq.ty<<' '<<qq.val<<' '<<qq.id<<'\n';
	}
	*/
	if(x+y==n)
	{
		for(auto qry:Q)
		{
			if(qry.ty==1) ans[qry.id]=pt[qry.val];
		}
		return ;
	}
	dsu.init();
	int X = x+(n-x-y)/2+1; int Y = n+1-X; //X+Y=N+1 
	//cerr<<X<<' '<<Y<<'\n';
	vector<query> up,right;
	priority_queue<ii,vector<ii>,greater<ii> > xcoord,ycoord;
	for(auto qry:Q)
	{
		//cerr<<qry.ty<<' '<<qry.val<<' '<<qry.id<<' '<<pt.size()<<'\n';
		//cerr<<dsu.val.size()<<'\n';
		if(qry.ty==1)
		{
			int ptid = qry.val;
			if(pt[ptid].fi>=X) right.pb(qry);
			else if(pt[ptid].se>=Y) up.pb(qry);
			else
			{
				//cerr<<"QUERY OF ID "<<qry.id<<" HAS BEEN ANSWERED\n";
				ans[qry.id]=getcoord(ptid);
			}
		}
		else if(qry.ty==2)
		{
			//horizontal motion
			int L = qry.val;
			if(L>=Y) //everything in range with x < n-l gets swept to the right. note that n-L<=n-Y is still in the range, so our points don't get pushed outside the box yet
			{
				int newx = n-L;
				int curid = dsu.add(newx,-1);
				while(!xcoord.empty())
				{
					int tpx = xcoord.top().fi;
					if(tpx>=n-L) break;
					curid=dsu.merge(curid,xcoord.top().se);
					xcoord.pop();
				}
				xcoord.push({newx,curid});
				up.pb(qry);
			}
			else
			{
				//ycoord<=L suffer
				while(!ycoord.empty())
				{
					int tpy = ycoord.top().fi;
					if(tpy>L) break;
					int dsuid = ycoord.top().se; ycoord.pop();
					//for all the points with this coordinate
					for(int p:dsu.pset[dsuid]) //a point gets traversed at most log (M+Q) times here and under log N recursive calls
					{
						p/=2;
						if(!pushed[p])
						{
							pt[p] = getcoord(p);
							pt[p].fi = n-L;
							right.pb(query(4,p,-1)); //new point position later
							pushed[p]=1;
						}
					}
				}
				right.pb(qry);
			}
		}
		else if(qry.ty==3)
		{
			int L = qry.val;
			if(L>=X) 
			{
				int newy = n-L;
				int curid = dsu.add(newy,-1);
				while(!ycoord.empty())
				{
					int tpy = ycoord.top().fi;
					if(tpy>=n-L) break;
					curid=dsu.merge(curid,ycoord.top().se);
					ycoord.pop();
				}
				ycoord.push({newy,curid});
				right.pb(qry);
			}
			else
			{
				while(!xcoord.empty())
				{
					int tpx = xcoord.top().fi;
					//cerr<<tpx<<'\n';
					if(tpx>L) break;
					int dsuid = xcoord.top().se; xcoord.pop();
					//for all the points with this coordinate
					for(int p:dsu.pset[dsuid]) //a point gets traversed at most log (M+Q) times here and under log N recursive calls
					{
						p/=2;
						if(!pushed[p])
						{
							pt[p] = getcoord(p);
							pt[p].se = n-L;
							//cerr<<pt[p].fi<<' '<<pt[p].se<<'\n';
							up.pb(query(4,p,-1)); //new point position later
							pushed[p]=1;
						}
					}
				}
				up.pb(qry);
			}
		}
		else
		{
			int ptid = qry.val;
			pushed[ptid]=0; //reset point
			int x = pt[ptid].fi; int y = pt[ptid].se;
			if(y>=Y){pushed[ptid]=1; up.pb(qry);}
			else if(x>=X){pushed[ptid]=1; right.pb(qry);}
			//the point belongs here 
			else
			{
				int xid = dsu.add(x,2*ptid);
				int yid = dsu.add(y,2*ptid+1);
				xcoord.push({x,xid});
				ycoord.push({y,yid});
			}
		}
	}
	solve(X,y,right); solve(x,Y,up);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m>>q;
	vi T;
	for(int i=0;i<m;i++)
	{
		int x,y; cin>>x>>y;
		pt.pb({x,y}); T.pb(0);
		queries.pb(query(4,i,-1));
	}
	for(int i=0;i<q;i++)
	{
		int t; cin>>t;
		if(t==4)
		{
			int x,y; cin>>x>>y;
			queries.pb(query(4,pt.size(),-1));
			pt.pb({x,y});
			continue;
		}
		int val; cin>>val;
		if(t==1) val--;
		queries.pb(query(t,val,i));
	}
	for(int i=0;i<q;i++) ans[i]={-1,-1};
	solve(0,0,queries);
	for(int i=0;i<q;i++)
	{
		if(ans[i].fi>=0) cout<<ans[i].fi<<' '<<ans[i].se<<'\n';
	}
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25