Submission #1039809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039809		AmirAli_H1	Comparing Plants (IOI20_plants)	C++17	30 / 100	796 ms	131808 KiB

plants

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node {
	ll lazy; pll min;
};

const int maxn = 2e5 + 7;
const int maxlg = 20;
const ll oo = 1e9 + 7;

int n, k;
int A[maxn], val[maxn];
set<int> st, stx; node t[4 * maxn];
int val1[maxn][maxlg], val2[maxn][maxlg];
pii up1[maxn][maxlg], up2[maxn][maxlg];
set<pii> stw; int arr[maxn];

bool cmp(int i, int j) {
	return (val[i] > val[j]);
}

void build(int v, int tl, int tr) {
	t[v].lazy = 0;
	if (tr - tl == 1) {
		t[v].min = Mp(A[tl], tl);
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v].min = min(t[2 * v + 1].min, t[2 * v + 2].min); t[v].min.F += t[v].lazy;
}

void add_val(int v, int tl, int tr, int l, int r, ll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	if (l == tl && r == tr) {
		t[v].min.F += x; t[v].lazy += x;
		return ;
	}
	int mid = (tl + tr) / 2;
	add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
	t[v].min = min(t[2 * v + 1].min, t[2 * v + 2].min); t[v].min.F += t[v].lazy;
}

void checkx(int j) {
	stx.erase(j); int d = 0;
	auto it = st.lower_bound(j);
	if (it != st.begin()) {
		it--; d = (j - *it);
	}
	else d = (j - *st.rbegin() + n);
	if (d >= k) stx.insert(j);
}

void addx(int j) {
	st.insert(j); checkx(j);
	if (len(st) == 1) return ;
	auto it = st.upper_bound(j);
	if (it != st.end()) checkx(*it);
	else checkx(*st.begin());
}

int get_val1(int v, ll x) {
	int res = 0;
	for (int j = maxlg - 1; j >= 0; j--) {
		if (val1[v][j] <= x) {
			res += up1[v][j].F;
			v = up1[v][j].S;
		}
	}
	return res;
}

int get_val2(int v, ll x) {
	int res = 0;
	for (int j = maxlg - 1; j >= 0; j--) {
		if (val2[v][j] <= x) {
			res += up2[v][j].F;
			v = up2[v][j].S;
		}
	}
	return res;
}

void delx(int j) {
	st.erase(j); stx.erase(j);
	if (len(st) == 0) return ;
	auto it = st.upper_bound(j);
	if (it != st.end()) checkx(*it);
	else checkx(*st.begin());
}

void init(int Kx, vector<int> Ax) {
	n = len(Ax); k = Kx;
	
	for (int i = 0; i < n; i++) A[i] = Ax[i];
	build(0, 0, n);
	
	int sz = 0;
	while (sz < n) {
		while (t[0].min.F == 0) {
			int j = t[0].min.S;
			add_val(0, 0, n, j, j + 1, oo);
			addx(j);
		}
		int j = *stx.begin(); val[j] = sz++;
		int x1 = min(j, k - 1), x2 = (k - 1) - x1;
		add_val(0, 0, n, j - x1, j, -1);
		add_val(0, 0, n, n - x2, n, -1);
		delx(j);
	}
	
	stw.clear();
	for (int j = 0; j < k; j++) stw.insert(Mp(val[j], j));
	for (int i = 0; i < n; i++) {
		int j = (i + k - 1) % n, r = -1;
		
		auto it = stw.upper_bound(Mp(val[i], oo));
		if (it != stw.end()) r = (*it).S;
		else r = i;
		up1[i][0] = Mp((r - i + n) % n, r);
		val1[i][0] = val[r];
		
		it = stw.upper_bound(Mp(val[j], oo));
		if (it != stw.end()) r = (*it).S;
		else r = j;
		up2[j][0] = Mp((j - r + n) % n, r);
		val2[j][0] = val[r];
		
		stw.erase(Mp(val[i], i));
		r = (i + k) % n;
		stw.insert(Mp(val[r], r));
	}
	
	iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
	for (int i = 0; i < n; i++) {
		int v = arr[i];
		for (int j = 1; j < maxlg; j++) {
			int u = up1[v][j - 1].S;
			up1[v][j] = Mp(up1[v][j - 1].F + up1[u][j - 1].F, up1[u][j - 1].S);
			val1[v][j] = val1[u][j - 1];
			
			u = up2[v][j - 1].S;
			up2[v][j] = Mp(up2[v][j - 1].F + up2[u][j - 1].F, up2[u][j - 1].S);
			val2[v][j] = val2[u][j - 1];
		}
	}
	
	return ;
}

int compare_plants(int x, int y) {
	if (val[x] < val[y]) {
		int d1 = (y - x + n) % n;
		int d2 = (x - y + n) % n;
		if (get_val1(x, val[y]) < d1 && get_val2(x, val[y]) < d2) return 0;
	}
	else {
		int d1 = (x - y + n) % n;
		int d2 = (y - x + n) % n;
		if (get_val1(y, val[x]) < d1 && get_val2(y, val[x]) < d2) return 0;
	}
	
	if (val[x] < val[y]) return 1;
	else return -1;
}

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