Submission #260777

#	Time	Username	Problem	Language	Result	Execution time	Memory
260777		amoo_safar	Sweeping (JOI20_sweeping)	C++17	0 / 100	6394 ms	1057912 KiB

sweeping

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
//#define int long long

using namespace std;

const int N = 15e5 + 10;
const int SGN = 45e5 + 2;

int lc[SGN], rc[SGN], la = 0;

vector<int> GX[N], GY[N];
int parX[N], parY[N], X[N], Y[N], wh[N], lapo = 0;
int FindX(int u){ return parX[u] = (parX[u] == u ? u : FindX(parX[u])); }
int FindY(int u){ return parY[u] = (parY[u] == u ? u : FindY(parY[u])); }
int GetX(int u){ return X[FindX(u)]; }
int GetY(int u){ return Y[FindY(u)]; }

void UniteX(int u, int v){
	//cerr << "# " << u << ' ' << v << '\n';
	u = FindX(u); v = FindX(v);
	if(u == v) return ;
	if(pair<int, int>(GetY(u), u) < pair<int, int>(GetY(v), v)) swap(u, v);
	parX[v] = u;
	GX[u].pb(v);
}

/*
void UniteY(int u, int v){
	u = FindY(u); v = FindY(v);
	if(u == v) return ;
	if(GetX(u) < GetX(v)) swap(u, v);
	parY[v] = u;
	GY[u].pb(v);
}
*/
struct CMPX {
	bool operator ()(int i, int j) const {
		if(GetX(i) != GetX(j))
			return GetX(i) < GetX(j);
		return i < j;
	}
};
struct CMPY {
	bool operator ()(int i, int j) const {
		if(GetY(i) != GetY(j))
			return GetY(i) < GetY(j);
		return i < j;
	}
};
set<int, CMPX> stX[SGN];
set<int, CMPY> stY[SGN];

int n, m, Q;
vector<int> vis;
void DFSY(int u, int id){
	if(wh[u] != id) return ;
	assert(GY[u].empty());

	vis.pb(u);
	for(auto adj : GY[u])
		DFSY(adj, id);
}

void Ins(int id, int po, int X0, int Y0){
	

	assert(id < SGN);
	int L = n - (X0 + Y0);
	int X1 = X0 + (L / 2);
	int Y1 = Y0 + ((L + 1) / 2);
	if(X[po] > X1){
		if(lc[id] == 0) lc[id] = ++la;
		Ins(lc[id], po, X1, Y0);
	} else if(Y[po] > Y1){
		if(rc[id] == 0) rc[id] = ++la;
		Ins(rc[id], po, X0, Y1);
	} else {
		//cerr << "ins: " << po << ' ' << id << '\n'; 
		wh[po] = id;
		parX[po] = po; parY[po] = po;
		stX[id].insert(po); stY[id].insert(po);
		GX[po].clear(); GY[po].clear();
	}
}

vector<int> Un;

void H(int id, int l, int X0, int Y0){
	if(l <= 0) return ;
	//if(id == 3) debug(l);
	//cerr << "H: " << id << ' ' << l << ' ' << X0 << ' ' << Y0 << '\n';
	int L = n - (X0 + Y0);
	int X1 = X0 + (L / 2);
	int Y1 = Y0 + ((L + 1) / 2);
	int rt, mv = L - l;
	assert(L > 1);
	//if(l == L) return ;
	//assert(l <= L);
	if(Y1 - Y0 <= l){ // shift
		//cerr << "! " << mv << ' ' << X0 << ' ' << Y0 << ' ' << '\n' << '\n';
		Un.clear();
		//cerr << "list: ";
		//for(auto po : stX[id]) cerr << po << ' ';
		//cerr << '\n';
		for(auto po : stX[id]){
			if(GetX(po) > X0 + mv) break;
			Un.pb(po);
			//cerr << "% " << po << '\n';
		}

		for(auto u : Un) stX[id].erase(u);
		
		for(int i = 0; i + 1 < (int) Un.size(); i++) UniteX(Un[i], Un[i + 1]);
		if(!Un.empty()){
			rt = FindX(Un.back());
			X[rt] = X0 + mv;
			stX[id].insert(rt);
		}
		for(auto u : Un){
			assert(GetX(u) == X0 + mv);
		}
		/*
		for(auto u : Un){
			X[u] = X0 + mv;
			stX[id].insert(u);
		}
		*/
		if(rc[id] != 0)
			H(rc[id], l - (Y1 - Y0), X0, Y1);
	} else { // remove
		vis.clear();
		for(auto po : stY[id]){
			if(GetY(po) > Y0 + l) break;
			DFSY(po, id);
			//vis.pb(po);
		}
		//cerr << "vis: ";
		//for(auto x : vis) cerr << x << '\n';
		//cerr << '\n';
		for(auto u : vis) stY[id].erase(u), stX[id].erase(u);
		for(auto u : vis) X[u] = X0 + mv, Y[u] = GetY(u);
		assert(X0 + mv > X1);

		if(!vis.empty()){
			for(auto u : vis)
				Ins(0, u, 0, 0);
		}
		if(lc[id] != 0)
			H(lc[id], l, X1, Y0);
		
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> Q;
	for(int i = 0; i < m; i++){
		lapo ++;
		cin >> X[lapo] >> Y[lapo];
		Ins(0, lapo, 0, 0);
	}
	//cerr << '\n';
	int type, Li, Pi;
	for(int i = 1; i <= Q; i++){
		if(i % 1000 == 0) debug(i);
		cin >> type;
		assert(type != 3);
		if(type == 4){
			lapo ++;
			cin >> X[lapo] >> Y[lapo];
			Ins(0, lapo, 0, 0);
		}
		if(type == 2){
			cin >> Li;
			H(0, Li, 0, 0);
			/*for(int j = 1; j <= lapo; j++)
				if(GetY(j) <= Li)
					X[j] = max(X[j], n - Li);
			*/
		}
		if(type == 1){
			cin >> Pi;
			cout << GetX(Pi) << ' ' << GetY(Pi) << '\n';
		}
	}
	//cerr << wh[2] << ' ' << lc[lc[ lc[0] ] ]  << '\n';
	return 0;
}

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