oj.uz

Submission #260765

# Submission time Handle Problem Language Result Execution time Memory
260765 2020-08-10T21:17:04 Z amoo_safar Sweeping (JOI20_sweeping) C++17
0 / 100
 3743 ms 1221996 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'

using namespace std;

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

int lc[N], rc[N], 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(GetY(u) < GetY(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){
		if(GetX(i) != GetX(j))
			return GetX(i) < GetX(j);
		return i < j;
	}
};
struct CMPY {
	bool operator ()(int i, int j){
		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 Ins(int id, int po, int X0, int Y0){
	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(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);
		}
		if(rc[id])
			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);
		}
		//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] = X1, Y[u] = GetY(u);
		
		if(!vis.empty()){
			if(!lc[id]) lc[id] = ++la;
			for(auto u : vis)
				Ins(lc[id], u, X1, Y0);
			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++){
		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);
		}
		if(type == 1){
			cin >> Pi;
			cout << GetX(Pi) << ' ' << GetY(Pi) << '\n';
			//break;
		}
	}
	//cerr << wh[2] << ' ' << lc[lc[ lc[0] ] ]  << '\n';
	return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3743 ms 737344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

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