oj.uz

Submission #260781

# Submission time Handle Problem Language Result Execution time Memory
260781 2020-08-11T01:13:48 Z amoo_safar Sweeping (JOI20_sweeping) C++17
65 / 100
 13714 ms 611584 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 = 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/3];
set<int, CMPY> stY[SGN/3];

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

# Verdict Execution time Memory Grader output
1 Correct 153 ms 212216 KB Output is correct
2 Correct 153 ms 211960 KB Output is correct
3 Correct 148 ms 212344 KB Output is correct
4 Correct 166 ms 212216 KB Output is correct
5 Correct 154 ms 212088 KB Output is correct
6 Correct 146 ms 212088 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6081 ms 611584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6008 ms 294216 KB Output is correct
2 Correct 6846 ms 310264 KB Output is correct
3 Correct 1988 ms 301048 KB Output is correct
4 Correct 7293 ms 345272 KB Output is correct
5 Correct 6784 ms 317800 KB Output is correct
6 Correct 4890 ms 309780 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6008 ms 294216 KB Output is correct
2 Correct 6846 ms 310264 KB Output is correct
3 Correct 1988 ms 301048 KB Output is correct
4 Correct 7293 ms 345272 KB Output is correct
5 Correct 6784 ms 317800 KB Output is correct
6 Correct 4890 ms 309780 KB Output is correct
7 Correct 6789 ms 314156 KB Output is correct
8 Correct 6057 ms 313692 KB Output is correct
9 Correct 6092 ms 313856 KB Output is correct
10 Correct 4981 ms 301784 KB Output is correct
11 Correct 9690 ms 325600 KB Output is correct
12 Correct 13714 ms 319388 KB Output is correct
13 Correct 13292 ms 317800 KB Output is correct
14 Correct 292 ms 215672 KB Output is correct
15 Correct 2975 ms 294352 KB Output is correct
16 Correct 5307 ms 312036 KB Output is correct
17 Correct 5391 ms 314120 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 212216 KB Output is correct
2 Correct 153 ms 211960 KB Output is correct
3 Correct 148 ms 212344 KB Output is correct
4 Correct 166 ms 212216 KB Output is correct
5 Correct 154 ms 212088 KB Output is correct
6 Correct 146 ms 212088 KB Output is correct
7 Runtime error 6081 ms 611584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -