oj.uz

Submission #211783

# Submission time Handle Problem Language Result Execution time Memory
211783 2020-03-21T09:07:59 Z zscoder Sweeping (JOI20_sweeping) C++17
100 / 100
 4813 ms 350216 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1280 KB Output is correct
2 Correct 15 ms 984 KB Output is correct
3 Correct 8 ms 1152 KB Output is correct
4 Correct 16 ms 1332 KB Output is correct
5 Correct 14 ms 1408 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3364 ms 137772 KB Output is correct
2 Correct 3291 ms 131208 KB Output is correct
3 Correct 3271 ms 132508 KB Output is correct
4 Correct 2811 ms 201228 KB Output is correct
5 Correct 4399 ms 158384 KB Output is correct
6 Correct 4115 ms 177704 KB Output is correct
7 Correct 3287 ms 131460 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3350 ms 154020 KB Output is correct
2 Correct 3371 ms 161112 KB Output is correct
3 Correct 2595 ms 182148 KB Output is correct
4 Correct 3370 ms 287640 KB Output is correct
5 Correct 3418 ms 237812 KB Output is correct
6 Correct 3061 ms 156004 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3350 ms 154020 KB Output is correct
2 Correct 3371 ms 161112 KB Output is correct
3 Correct 2595 ms 182148 KB Output is correct
4 Correct 3370 ms 287640 KB Output is correct
5 Correct 3418 ms 237812 KB Output is correct
6 Correct 3061 ms 156004 KB Output is correct
7 Correct 3358 ms 144412 KB Output is correct
8 Correct 3337 ms 151132 KB Output is correct
9 Correct 3346 ms 139072 KB Output is correct
10 Correct 3080 ms 177560 KB Output is correct
11 Correct 3706 ms 245112 KB Output is correct
12 Correct 4355 ms 198288 KB Output is correct
13 Correct 4226 ms 324756 KB Output is correct
14 Correct 154 ms 55624 KB Output is correct
15 Correct 714 ms 117852 KB Output is correct
16 Correct 3286 ms 147456 KB Output is correct
17 Correct 3627 ms 152204 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1280 KB Output is correct
2 Correct 15 ms 984 KB Output is correct
3 Correct 8 ms 1152 KB Output is correct
4 Correct 16 ms 1332 KB Output is correct
5 Correct 14 ms 1408 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Correct 3364 ms 137772 KB Output is correct
8 Correct 3291 ms 131208 KB Output is correct
9 Correct 3271 ms 132508 KB Output is correct
10 Correct 2811 ms 201228 KB Output is correct
11 Correct 4399 ms 158384 KB Output is correct
12 Correct 4115 ms 177704 KB Output is correct
13 Correct 3287 ms 131460 KB Output is correct
14 Correct 3350 ms 154020 KB Output is correct
15 Correct 3371 ms 161112 KB Output is correct
16 Correct 2595 ms 182148 KB Output is correct
17 Correct 3370 ms 287640 KB Output is correct
18 Correct 3418 ms 237812 KB Output is correct
19 Correct 3061 ms 156004 KB Output is correct
20 Correct 3358 ms 144412 KB Output is correct
21 Correct 3337 ms 151132 KB Output is correct
22 Correct 3346 ms 139072 KB Output is correct
23 Correct 3080 ms 177560 KB Output is correct
24 Correct 3706 ms 245112 KB Output is correct
25 Correct 4355 ms 198288 KB Output is correct
26 Correct 4226 ms 324756 KB Output is correct
27 Correct 154 ms 55624 KB Output is correct
28 Correct 714 ms 117852 KB Output is correct
29 Correct 3286 ms 147456 KB Output is correct
30 Correct 3627 ms 152204 KB Output is correct
31 Correct 3410 ms 172052 KB Output is correct
32 Correct 3557 ms 141596 KB Output is correct
33 Correct 3394 ms 119392 KB Output is correct
34 Correct 3628 ms 155704 KB Output is correct
35 Correct 3720 ms 143528 KB Output is correct
36 Correct 2994 ms 176044 KB Output is correct
37 Correct 4813 ms 323744 KB Output is correct
38 Correct 4544 ms 350216 KB Output is correct
39 Correct 3962 ms 278280 KB Output is correct
40 Correct 3209 ms 158136 KB Output is correct