Submission #1239530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239530		AMnu	Comparing Plants (IOI20_plants)	C++20	100 / 100	529 ms	62012 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;

const int MAXN = 2e5+5, LOG = 18;

int N, K, T, H[MAXN], L[MAXN][LOG], R[MAXN][LOG];
vector <int> A = {0};
set <pii> S;

struct tree {
	int L, R, val, lz;
	tree *lef, *rig;
	
	tree(int x,int y) {
		L = x; R = y;
		lz = 0;
		if (L == R) {
			val = A[L];
			return;
		}
		int mid=(L+R)/2;
		lef = new tree(L,mid);
		rig = new tree(mid+1,R);
		val = min(lef->val,rig->val);
	}
	
	void push() {
		if (lz) {
			lef->val -= lz;
			lef->lz += lz;
			rig->val -= lz;
			rig->lz += lz;
			lz = 0;
		}
	}
	
	int find(int x,int y) {
		if (x > R || y < L || val) {
			return -1;
		}
		if (L == R) {
			return L;
		}
		push();
		int res = lef->find(x,y);
		if (res != -1) {
			return res;
		}
		return rig->find(x,y);
	}
	
	void update(int x,int y) {
		if (x > R || y < L) {
			return;
		}
		if (x <= L && y >= R) {
			val--;
			lz++;
			return;
		}
		push();
		lef->update(x,y);
		rig->update(x,y);
		val = min(lef->val,rig->val);
	}
	
	void del(int x) {
		if (L == R) {
			val = MAXN;
			return;
		}
		push();
		int mid = (L+R)/2;
		if (x <= mid) {
			lef->del(x);
		}
		else {
			rig->del(x);
		}
		val = min(lef->val,rig->val);
	}
} root(0,0);

void dfs(int x) {
	while (1) {
		int y = root.find(x-K+1,x-1);
		if (y == -1) {
			break;
		}
		dfs(y);
	}
	while (1) {
		int y = root.find(x+N-K+1,N-1);
		if (y == -1) {
			break;
		}
		dfs(y);
	}
	H[x] = T;
	T--;
	root.del(x);
	root.update(x-K+1,x-1);
	root.update(x+N-K+1,N-1);
}

void init(int k,vector<int> r) {
	K = k;
	A = r;
	T = N = A.size();
	root = tree(0,N-1);
	while (T) {
		int x = root.find(0,N-1);
		dfs(x);
	}
	for (int i=0;i<K-1;i++) {
		S.insert({H[i],i});
	}
	for (int i=0;i<N;i++) {
		S.erase({H[i],i});
		S.insert({H[(i+K-1)%N],(i+K-1)%N});
		auto it = S.lower_bound({H[i],0});
		if (it != S.begin()) {
			it--;
			R[i][0] = (it->se - i + N) % N;
		}
		it = S.lower_bound({H[(i+K)%N],0});
		if (it != S.begin()) {
			it--;
			L[(i+K)%N][0] = (i + K - it->se + N) % N;
		}
	}
	for (int i=1;i<LOG;i++) {
		for (int j=0;j<=N;j++) {
			L[j][i] = min(N, L[j][i-1] + L[(j-L[j][i-1]+N)%N][i-1]);
			R[j][i] = min(N, R[j][i-1] + R[(j+R[j][i-1])%N][i-1]);
		}
	}
}

bool taller(int x,int y) {
	int z = x;
	for (int i=LOG-1;i>=0;i--) {
		if (L[z][i] < (z-y+N)%N) {
			z = (z-L[z][i]+N)%N;
		}
	}
	if ((z-y+N)%N < K && H[z] > H[y]) {
		return 1;
	}
	z = x;
	for (int i=LOG-1;i>=0;i--) {
		if (R[z][i] < (y-z+N)%N) {
			z = (z+R[z][i])%N;
		}
	}
	if ((y-z+N)%N < K && H[z] > H[y]) {
		return 1;
	}
	return 0;
}

int compare_plants(int x,int y) {
	if (taller(x,y)) {
		return 1;
	}
	if (taller(y,x)) {
		return -1;
	}
	return 0;
}

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