Submission #1039790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039790		AmirAli_H1	Comparing Plants (IOI20_plants)	C++17	44 / 100	259 ms	36944 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 ll oo = 1e9 + 7;

int n, k;
int A[maxn], val[maxn];
set<int> st, stx;
node t[4 * maxn];

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());
}

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);
	}
	
	return;
}

int compare_plants(int x, int y) {
	if (val[x] < val[y]) return 1;
	else return -1;
}

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