oj.uz

답안 #260783

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260783 2020-08-11T01:16:30 Z amoo_safar 청소 (JOI20_sweeping) C++17
100 / 100
 15397 ms 1633896 KB 
// 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 = 15e6 + 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 ;

	vis.pb(u);
	for(auto adj : GY[u])
		DFSY(adj, id);
}
void DFSX(int u, int id){
	if(wh[u] != id) return ;

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

void Ins(int id, int po, int X0, int Y0){
	if(X[po] + Y[po] == n){
		parX[po] = parY[po] = po;
		GX[po].clear(); GY[po].clear();
		wh[po] = -1;
		return ;
	}

	assert(id < SGN/3);
	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;
	//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){
			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);
		}
		
		for(auto u : vis) stY[id].erase(u), stX[id].erase(u);
		for(auto u : vis) X[u] = X0 + mv, Y[u] = GetY(u);
		
		if(!vis.empty()){
			for(auto u : vis)
				Ins(0, u, 0, 0);
		}
		
		if(lc[id] != 0)
			H(lc[id], l, X1, Y0);
	}
}


void V(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;
	//if(l == L) return ;
	//assert(l <= L);
	if(X1 - X0 <= l){ // shift
		//cerr << "! " << mv << ' ' << X0 << ' ' << Y0 << ' ' << '\n' << '\n';
		Un.clear();
		//cerr << "list: ";
		//for(auto po : stX[id]) cerr << po << ' ';
		//cerr << '\n';
		for(auto po : stY[id]){
			if(GetY(po) > Y0 + mv) break;
			Un.pb(po);
			//cerr << "% " << po << '\n';
		}

		for(auto u : Un) stY[id].erase(u);
		
		for(int i = 0; i + 1 < (int) Un.size(); i++) UniteY(Un[i], Un[i + 1]);
		if(!Un.empty()){
			rt = FindY(Un.back());
			Y[rt] = Y0 + mv;
			stY[id].insert(rt);
		}
		/*
		for(auto u : Un){
			X[u] = X0 + mv;
			stX[id].insert(u);
		}
		*/
		if(lc[id] != 0)
			V(lc[id], l - (X1 - X0), X1, Y0);
	} else { // remove
		vis.clear();
		for(auto po : stX[id]){
			if(GetX(po) > X0 + l) break;
			DFSX(po, id);
			//vis.pb(po);
		}
		for(auto u : vis) stY[id].erase(u), stX[id].erase(u);
		for(auto u : vis) Y[u] = Y0 + mv, X[u] = GetX(u);

		if(!vis.empty()){
			for(auto u : vis)
				Ins(0, u, 0, 0);
		}
		if(rc[id] != 0)
			V(rc[id], l, X0, Y1);
	}
}


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++){
		cin >> type;
		if(type == 4){
			lapo ++;
			cin >> X[lapo] >> Y[lapo];
			Ins(0, lapo, 0, 0);
		}
		if(type == 3){
			cin >> Li;
			V(0, Li, 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
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 893 ms 1480444 KB Output is correct
2 Correct 872 ms 1480056 KB Output is correct
3 Correct 880 ms 1480540 KB Output is correct
4 Correct 863 ms 1480312 KB Output is correct
5 Correct 873 ms 1480184 KB Output is correct
6 Correct 869 ms 1480184 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7363 ms 1578700 KB Output is correct
2 Correct 6612 ms 1577412 KB Output is correct
3 Correct 6896 ms 1577224 KB Output is correct
4 Correct 5910 ms 1560964 KB Output is correct
5 Correct 14680 ms 1584336 KB Output is correct
6 Correct 12135 ms 1574136 KB Output is correct
7 Correct 6347 ms 1575380 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7210 ms 1567908 KB Output is correct
2 Correct 8115 ms 1559072 KB Output is correct
3 Correct 2924 ms 1550444 KB Output is correct
4 Correct 8090 ms 1594600 KB Output is correct
5 Correct 7424 ms 1566928 KB Output is correct
6 Correct 5586 ms 1558584 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7210 ms 1567908 KB Output is correct
2 Correct 8115 ms 1559072 KB Output is correct
3 Correct 2924 ms 1550444 KB Output is correct
4 Correct 8090 ms 1594600 KB Output is correct
5 Correct 7424 ms 1566928 KB Output is correct
6 Correct 5586 ms 1558584 KB Output is correct
7 Correct 6820 ms 1563064 KB Output is correct
8 Correct 6465 ms 1562536 KB Output is correct
9 Correct 6721 ms 1562936 KB Output is correct
10 Correct 5659 ms 1551404 KB Output is correct
11 Correct 10111 ms 1574652 KB Output is correct
12 Correct 12724 ms 1568344 KB Output is correct
13 Correct 12871 ms 1566824 KB Output is correct
14 Correct 1086 ms 1483784 KB Output is correct
15 Correct 3298 ms 1550072 KB Output is correct
16 Correct 5821 ms 1560436 KB Output is correct
17 Correct 6164 ms 1562620 KB Output is correct

Subtask #5
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 893 ms 1480444 KB Output is correct
2 Correct 872 ms 1480056 KB Output is correct
3 Correct 880 ms 1480540 KB Output is correct
4 Correct 863 ms 1480312 KB Output is correct
5 Correct 873 ms 1480184 KB Output is correct
6 Correct 869 ms 1480184 KB Output is correct
7 Correct 7363 ms 1578700 KB Output is correct
8 Correct 6612 ms 1577412 KB Output is correct
9 Correct 6896 ms 1577224 KB Output is correct
10 Correct 5910 ms 1560964 KB Output is correct
11 Correct 14680 ms 1584336 KB Output is correct
12 Correct 12135 ms 1574136 KB Output is correct
13 Correct 6347 ms 1575380 KB Output is correct
14 Correct 7210 ms 1567908 KB Output is correct
15 Correct 8115 ms 1559072 KB Output is correct
16 Correct 2924 ms 1550444 KB Output is correct
17 Correct 8090 ms 1594600 KB Output is correct
18 Correct 7424 ms 1566928 KB Output is correct
19 Correct 5586 ms 1558584 KB Output is correct
20 Correct 6820 ms 1563064 KB Output is correct
21 Correct 6465 ms 1562536 KB Output is correct
22 Correct 6721 ms 1562936 KB Output is correct
23 Correct 5659 ms 1551404 KB Output is correct
24 Correct 10111 ms 1574652 KB Output is correct
25 Correct 12724 ms 1568344 KB Output is correct
26 Correct 12871 ms 1566824 KB Output is correct
27 Correct 1086 ms 1483784 KB Output is correct
28 Correct 3298 ms 1550072 KB Output is correct
29 Correct 5821 ms 1560436 KB Output is correct
30 Correct 6164 ms 1562620 KB Output is correct
31 Correct 6046 ms 1587284 KB Output is correct
32 Correct 6993 ms 1594868 KB Output is correct
33 Correct 3347 ms 1616224 KB Output is correct
34 Correct 8271 ms 1613968 KB Output is correct
35 Correct 8409 ms 1613984 KB Output is correct
36 Correct 6471 ms 1575952 KB Output is correct
37 Correct 15397 ms 1633896 KB Output is correct
38 Correct 12963 ms 1596012 KB Output is correct
39 Correct 10940 ms 1592936 KB Output is correct
40 Correct 6292 ms 1590212 KB Output is correct