Submission #432164

#	Time	Username	Problem	Language	Result	Execution time	Memory
432164		peuch	Comparing Plants (IOI20_plants)	C++17	0 / 100	4017 ms	31688 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;

int N;
bool sub1;
vector<int> esq, dir, id;

vector<pair<int, int> > mini;
vector<int> lz;
vector<int> R;

vector<pair<pair<int, int>, int> > seg;
vector<int> lz2;

vector<int> rep, tam;

int find(int a){
	if(rep[a] == a) return a;
	return rep[a] = find(rep[a]);
}

void uni(int a, int b){
	a = find(a);
	b = find(b);
	if(a == b) return;
	if(tam[a] < tam[b]) swap(a, b);
	rep[b] = a;
	tam[a] += tam[b];
}

void build(int pos, int ini, int fim){
	lz[pos] = lz2[pos] = 0;
	if(ini == fim){
		mini[pos] = make_pair(R[ini], ini);
		seg[pos] = make_pair(make_pair(1, 0), ini);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	build(e, ini, mid);
	build(d, mid + 1, fim);
	mini[pos] = min(mini[e], mini[d]);
	seg[pos] = min(seg[e], seg[d]);
}

void refresh2(int pos, int ini, int fim){
	if(lz2[pos] == 0) return;
	seg[pos].first.second += lz2[pos];
	if(ini != fim){
		int e = pos << 1, d = e | 1;
		lz2[e] += lz2[pos];
		lz2[d] += lz2[pos];
	}
	lz2[pos] = 0;
}

void activate(int pos, int ini, int fim, int id){
	refresh2(pos, ini, fim);
	if(ini > id || fim < id) return;
	if(ini == fim){
		seg[pos].first.first ^= 1;
		refresh2(pos, ini, fim);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	activate(e, ini, mid, id);
	activate(d, mid + 1, fim, id);
	seg[pos] = min(seg[e], seg[d]);
}

void update2(int pos, int ini, int fim, int p, int q, int val){
	refresh2(pos, ini, fim);
	if(ini > q || fim < p) return;
	if(ini >= p && fim <= q){
		lz2[pos] += val;
		refresh2(pos, ini, fim);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	update2(e, ini, mid, p, q, val);
	update2(d, mid + 1, fim, p, q, val);
	seg[pos] = min(seg[e], seg[d]);
}

void refresh(int pos, int ini, int fim){
	if(lz[pos] == 0) return;
	mini[pos].first += lz[pos];
	if(ini != fim){
		int e = pos << 1, d = e | 1;
		lz[e] += lz[pos];
		lz[d] += lz[pos];
	}
	lz[pos] = 0;
}

void update(int pos, int ini, int fim, int p, int q, int val){
	refresh(pos, ini, fim);
	if(ini > q || fim < p) return;
	if(ini >= p && fim <= q){
		lz[pos] += val;
		refresh(pos, ini, fim);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	update(e, ini, mid, p, q, val);
	update(d, mid + 1, fim, p, q, val);
	mini[pos] = min(mini[e], mini[d]);
}

void init(int k, vector<int> r) {
	sub1 = false;
	R = r;
	N = R.size();
	if(sub1){
		esq = vector<int> (N);
		dir = vector<int> (N);
		int ini;
		for(ini = 0; ini < N; ini++)
			if(r[ini] == 0) break;
		ini++;
		ini %= N;
		esq[ini] = 0;
		for(int i = ini + 1; i != ini; i++, i %= N){
			int ant = i - 1;
			if(ant < 0) ant += N;
			esq[i] = esq[ant] + 1;
			if(r[ant] == 0) esq[i] = 0;
		}
		
		for(ini = 0; ini < N; ini++)
			if(r[ini] == 1) break;
		dir[ini] = 0;
		for(int i = (ini + N - 1) % N; i != ini; i += N - 1, i %= N){
			int nex = i + 1;
			if(nex >= N) nex -= N;
			dir[i] = dir[nex] + 1;
			if(r[i] == 1) dir[i] = 0;
		}
		return;
	}
	mini = vector<pair<int, int> > (4 * N);
	seg = vector<pair<pair<int, int>, int> > (4 * N);
	lz = lz2 = vector<int> (4 * N);
	build(1, 0, N - 1);
	id = vector<int> (N);
	vector<int> marc(N);
	tam = vector<int> (2 * N);
	rep = vector<int> (2 * N);
	for(int i = 0; i < 2 * N; i++){
		rep[i] = i;
		tam[i] = 1;
	}
	for(int i = 0; i < N; i++){
		while(1){
			int in = mini[1].first;
			int idx = mini[1].second;
			if(in != 0) break;
			update(1, 0, N - 1, idx, idx, 1e8);
			activate(1, 0, N - 1, idx);
			update2(1, 0, N - 1, idx + 1, idx + k - 1, 1);
			update2(1, 0, N - 1, 0, idx + k - 1 - N, 1);
		}
		int idx = seg[1].second;
		update2(1, 0, N - 1, idx + 1, idx + k - 1, -1);
		update2(1, 0, N - 1, 0, idx + k - 1 - N, -1);
		activate(1, 0, N - 1, idx);
		update(1, 0, N - 1, idx - k + 1, idx - 1, -1);
		update(1, 0, N - 1, idx + N - k + 1, N - 1, -1);
		
		for(int i = idx; i != (idx + k) % N; i++, i %= N){
			if(marc[i]) continue;
			uni(2 * i, 2 * idx);
		}
		for(int i = idx; i != (idx + N - k) % N; i += N - 1, i %= N){
			if(marc[i]) continue;
			uni(2 * i + 1, 2 * idx + 1);
		}
		
		marc[idx] = 1;
		
		id[idx] = N - i;
	}
	return;
}

int compare_plants(int x, int y) {
	if(sub1){
		if(x + dir[x] >= y) return 1;
		if(x - esq[x] < 0 && (x + N - esq[x]) % N <= y) return 1;
		if(y - esq[y] <= x) return -1;
		if(y + dir[y] > N && (y + dir[y]) % N >= x) return -1;
		return 0;
	}
	if(find(2 * x) != find(2 * y) && find(2 * x + 1) != find(2 * y + 1)) return 0;
	else if(id[x] > id[y]) return 1;
	else return -1;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25