Submission #821677

#	Time	Username	Problem	Language	Result	Execution time	Memory
821677		Abrar_Al_Samit	Comparing Plants (IOI20_plants)	C++17	27 / 100	268 ms	19824 KiB

plants

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

const int nax = 2e5 + 2;
const int inf = 2e9;


int val[nax], n, k;
struct plant {
	int id;

	plant(int _id = 0) {
		id = _id;
	}

	bool operator<(plant b) const {
		if(id + k - 1 < n) {
			return b.id > id && b.id <= id + k - 1;
		} else {
			if(b.id < id) return (id + k - 1) % n >= b.id;
			else return b.id > id;
		}
	}
};

int stree[nax * 4], at[nax * 4], lztree[nax * 4], del;

void propagate(int v) {
	stree[v << 1] += lztree[v];
	stree[v << 1 | 1] += lztree[v];
	lztree[v << 1] += lztree[v];
	lztree[v << 1 | 1] += lztree[v];
	lztree[v] = 0;
}
void update(int L, int R, int l = 0, int r = n-1, int v = 1) {
	if(l >= L && r <= R) {
		lztree[v] += del;
		stree[v] += del;
		return;
	}
	if(l > R || r < L) return;
	propagate(v);

	int mid = (l + r) >> 1;
	update(L, R, l, mid, v << 1);
	update(L, R, mid+1, r, v << 1 | 1);

	stree[v] = min(stree[v << 1], stree[v << 1 | 1]);
	at[v] = (stree[v << 1] < stree[v << 1 | 1]) ? at[v << 1] : at[v << 1 | 1];
}
void upd(int L, int R) {
	if(L < 0) {
		update(0, R);
		L += n;
		update(L, n-1);
	} else {
		update(L, R);
	}
}
vector<int>R;
void build(int l = 0, int r = n-1, int v = 1) {
	if(l == r) {
		stree[v] = R[l];
		at[v] = l;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, v << 1);
	build(mid+1, r, v << 1 | 1);
	stree[v] = min(stree[v << 1], stree[v << 1 | 1]);
	at[v] = (stree[v << 1] < stree[v << 1 | 1]) ? at[v << 1] : at[v << 1 | 1];	
}

void init(int K, vector<int> r) {
	k = K;
	n = r.size();
	R = r;

	build();

	set<plant>cand;
	for(int tg=n; tg>=1; --tg) {
		while(stree[1]==0) {
			int mat = at[1];
			cand.insert(plant(mat));

			del = inf;
			upd(mat, mat);
		}

		plant mx = *cand.begin();
		cand.erase(mx);

		val[mx.id] = tg;
		del = -1;
		upd(mx.id - k + 1, mx.id);
	}
}

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

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