Submission #216257

#	Time	Username	Problem	Language	Result	Execution time	Memory
216257		ryansee	Sweeping (JOI20_sweeping)	C++14	0 / 100	12402 ms	999708 KiB

sweeping

#include "bits/stdc++.h"
using namespace std;
 
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
 
typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;
 
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (1500006) // change MAXN later
struct Query{
	ll t, ind, l, x, y, QI;
};vector<Query> Q;
ll n,m,q,cnt;
pi pos[MAXN],ans[MAXN];
vector<ll> v[MAXN*2];
struct ufds_ {
	int p[MAXN*2];
	void init(ll x) {
		FOR(i,0,x+1) p[i]=i, v[i].clear(), v[i].pb(i);
	}
	void merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y)return;
		if(siz(v[x])>siz(v[y]))swap(x,y);
		p[x]=y;
		for(auto i:v[x]) v[y].pb(i);
		v[x].clear();
	}
	int find(int x) { return (p[x]==x)?x:p[x]=find(p[x]); }
	bool same(int x,int y) { return find(x)==find(y); }
} ufds;
void dnc(ll x,ll y,vector<Query> Q){
	if(Q.empty())return;
	sort(all(Q),[](Query x,Query y){return x.QI<y.QI;});
	ll diff=n-x-y;
	if(diff == 0) { // do something(?) just answer the Queries(?)
		for(auto i:Q) if(i.t==1) ans[i.ind]={x,y};
		return;
	}
	ll X=x+(diff+1)/2, Y=y+diff/2+1, cnt=0, act=0;
	ufds.init(Q.size()*2+3);
	vector<bool> gone(Q.size(), 0);
	vector<Query> UP, RI;
	priority_queue<pi,vector<pi>,greater<pi>> px, py;
	map<ll,ll> gcnt, cntQ;
	vector<ll> xnow(Q.size(),0), ynow(Q.size(),0);
	for(auto i:Q) if(i.t==4) { xnow[cnt]=i.x, ynow[cnt]=i.y; gcnt[i.ind]=cnt; cntQ[cnt]=act; ++ cnt, ++ act; } else ++ act;
	cnt=0;
	for(auto i:Q){
		if(i.t==1){// reconsider index pls
			Query tmp = i;
			i.l=gcnt[i.l];
			auto D=[&](ll a,ll b,ll c,ll d){
				return a;
			};
			if(gone[i.l]){
				// decide whether to push Query into UP or RI
				if(xnow[D(ufds.find(i.l<<1|1),i.l<<1|1,ufds.find(i.l<<1),i.l<<1)>>1] >= X) { 
					assert(ynow[D(ufds.find(i.l<<1),i.l<<1,ufds.find(i.l<<1|1),i.l<<1|1)>>1] < Y);
					RI.pb(tmp);
				}else if(ynow[D(ufds.find(i.l<<1),i.l<<1,ufds.find(i.l<<1|1),i.l<<1|1)>>1] >= Y) {
					UP.pb(tmp);
				}else {
					// cerr<<x<<' '<<y<<'\n';
					assert(0);
				}
			}else{
				ans[i.ind]=pi(xnow[D(ufds.find(i.l<<1|1),i.l<<1|1,ufds.find(i.l<<1),i.l<<1)>>1],ynow[D(ufds.find(i.l<<1),i.l<<1,ufds.find(i.l<<1|1),i.l<<1|1)>>1]);
			}
		}else if(i.t==2){ // horizontal
			if(n-i.l >= X) { // protrudes
				RI.pb(i);
				// all y <= i.l, set gone = 1, push RI, rmbr to set xnow, cos queries need to go where to go
				while(py.size()) {
					if(py.top().f > i.l) break;
					ll x=py.top().s;
					py.pop();
					if(gone[x>>1])continue;
					assert(ufds.find(x)==x);
					xnow[x>>1]=n-i.l;assert(n-i.l>=X);
					auto tmp=i;
					for(auto i:v[x]) if(ufds.find(i)==x && !gone[i>>1]) {
						xnow[i>>1]=n-tmp.l, gone[i>>1]=1, RI.pb(Q[cntQ[i>>1]]);
					}
					for(auto i:v[x]) ufds.p[i]=i, v[i].clear(), v[i].pb(i), ufds.p[i-1]=i-1,v[i-1].clear(),v[i-1].pb(i-1);
				}
			}else {// def taller than square
				UP.pb(i);
				ll lst=-1;
				while(px.size()){
					if(px.top().f>n-i.l) break;
					ll x=px.top().s;
					px.pop();
					if(gone[x>>1])continue;
					if(~lst){
						ufds.merge(lst,x);
					}
					lst=x;
				}
				if(~lst) lst=ufds.find(lst), xnow[lst>>1]=n-i.l, px.emplace(xnow[lst>>1],lst);
			}
		}else if(i.t==3){ // vertical
			if(n-i.l>=Y){//protrudes
				UP.pb(i);
				while(px.size()){
					if(px.top().f>i.l)break;
					ll x=px.top().s;
					px.pop();
					if(gone[x>>1])continue;
					assert(ufds.find(x)==x);
					ynow[x>>1]=n-i.l;assert(n-i.l>=Y);
					auto tmp=i;
					for(auto i:v[x]) if(ufds.find(i) == x && !gone[i>>1]) {
						ynow[i>>1]=n-tmp.l, assert(ufds.find(i)==x), gone[i>>1]=1, UP.pb(Q[cntQ[i>>1]]);
					}
					for(auto i:v[x]) ufds.p[i]=i, v[i].clear(), v[i].pb(i),ufds.p[i+1]=i+1,v[i+1].clear(),v[i+1].pb(i+1);
				}
			}else{//def wider than sqaure
				RI.pb(i);
				ll lst=-1;
				while(py.size()){
					if(py.top().f>n-i.l)break;
					ll x=py.top().s;
					py.pop();
					if(gone[x>>1])continue;
					if(~lst) {
						ufds.merge(lst, x);
					}
					lst=x;
				}
				if(~lst) lst=ufds.find(lst), ynow[lst>>1]=n-i.l, py.emplace(ynow[lst>>1],lst);
			}
		}else{ // add new point
			if(i.x >= X) { assert(i.y < Y);
				gone[cnt]=1, RI.pb(i);
			}else if(i.y >= Y) { assert(i.x < X);
				gone[cnt]=1, UP.pb(i);
			}else{
				px.emplace(i.x, cnt<<1);
				py.emplace(i.y, cnt<<1|1);
			}
			++ cnt;
		}
	} // cannot change the array pos at the end, as in separate dncs, some moves might end up coming first
	// cerr<<X<<' '<<y<<" RI: ";
	// for(auto i:RI) cerr<<i.QI<<' ';
	// cerr<<'\n';
	// cerr<<x<<' '<<Y<<" UP: ";
	// for(auto i:UP) cerr<<i.QI<<' ';
	// cerr<<'\n';
	dnc(X,y,RI);
	dnc(x,Y,UP);
}
int main(){
	FAST
	cin>>n>>m>>q;
	FOR(i,1,m){
		++ cnt;
		cin>>pos[cnt].f>>pos[cnt].s;
		Q.pb({4,cnt,-1,pos[cnt].f,pos[cnt].s});
	}
	FOR(ii,1,q){
		ll t;cin>>t;
		if(t<=3){
			ll l;cin>>l;
			Q.pb({t,ii,l,-1,-1});
		}else{
			++ cnt;
			cin>>pos[cnt].f>>pos[cnt].s;
			Q.pb({4,cnt,-1,pos[cnt].f,pos[cnt].s});
		}
	}
	FOR(i,0,siz(Q)-1)Q[i].QI=i;
	mmst(ans,-1);
	dnc(0,0,Q);
	FOR(i,1,q)if(ans[i]!=pi(-1,-1))cout<<ans[i].f<<' '<<ans[i].s<<'\n';
}
/*
20 1 7
1 0
2 18
3 9
3 10
3 3
2 9
3 12
1 1
*/ 

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