Submission #1050488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050488		dozer	Comparing Plants (IOI20_plants)	C++14	44 / 100	438 ms	38228 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sp " "
#define endl "\n"
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 2000005

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;

int val[MAXN], lazy[4 * MAXN];

pii tree[4 * MAXN];

void push(int node, int l, int r){
	tree[node].st += lazy[node];
	if (l != r){
		lazy[LL] += lazy[node];
		lazy[RR] += lazy[node];
	}
	lazy[node] = 0;
}

void update(int node, int l, int r, int sl, int val){
	push(node, l, r);
	if (l > sl || r < sl) return;
	if (l == r){
		tree[node].st = val;
		return;
	}

	int mid = (l + r) / 2;
	update(LL, l, mid, sl, val);
	update(RR, mid + 1, r, sl, val);
	tree[node] = min(tree[LL], tree[RR]);
}

void update(int node, int l, int r, int sl, int sr, int val){
	push(node, l, r);
	if (l > sr || r < sl) return;
	if (l >= sl && r <= sr){
		lazy[node] += val;
		push(node, l, r);
		return;
	}

	int mid = (l + r) / 2;
	update(LL, l, mid, sl, sr, val);
	update(RR, mid + 1, r, sl, sr, val);
	tree[node] = min(tree[LL], tree[RR]);
}

void build(int node, int l, int r){
	tree[node] = {0, l};
	if (l == r) return;
	int mid = (l + r) / 2;
	build(LL, l, mid);
	build(RR, mid + 1, r);
}

pii query(int node, int l, int r, int sl, int sr){
	push(node, l, r);
	if (l > sr || r < sl) return {modulo, modulo};
	if (l >= sl && r <= sr) return tree[node];
	int mid = (l + r) / 2;
	return min(query(LL, l, mid, sl, sr), query(RR, mid + 1, r, sl, sr));
}


void init(int k, vector<int> r) {
	int n = r.size();
	vector<int> done(n, 0);
	set<int> todo;
	set<pii> dist;

	build(1, 0, n - 1);
	for (int i = 0; i < n; i++){
		update(1, 0, n - 1, i, r[i]);
	}
	

	auto add = [&](int x){
		if (todo.empty()){
			todo.insert(x);
			return;
		}
		if (todo.size() == 1){
			int tmp = *todo.begin();
			dist.insert({(x - tmp + n) % n, x});
			dist.insert({(tmp - x + n) % n, tmp});
			todo.insert(x);
			return;
		}

		auto it = todo.lower_bound(x);
		auto it2 = todo.lower_bound(x);
		if (it == todo.begin()){
			it = todo.lower_bound(*todo.rbegin());
		}
		else{
			it--;
		}
		if (it2 == todo.end()) it2 = todo.begin();
		int l = *it, r = *it2;
		dist.erase({(r - l + n) % n, r});
		dist.insert({(r - x + n) % n, r});
		dist.insert({(x - l + n) % n, x});
		todo.insert(x);
	};

	auto del = [&](int x){
		todo.erase(x);
		if (todo.empty()){
			return;
		}
		if (todo.size() == 1){
			int tmp = *todo.begin();
			dist.erase({(x - tmp + n) % n, x});
			dist.erase({(tmp - x + n) % n, tmp});
			return;
		}

		auto it = todo.lower_bound(x);
		auto it2 = todo.lower_bound(x);
		if (it == todo.begin()){
			it = todo.lower_bound(*todo.rbegin());
		}
		else{
			it--;
		}
		if (it2 == todo.end()) it2 = todo.begin();
		int l = *it, r = *it2;
		dist.insert({(r - l + n) % n, r});
		dist.erase({(r - x + n) % n, r});
		dist.erase({(x - l + n) % n, x});
	};


	auto recompute = [&](){
		int start = 0;
		while(start < n){
			pii tmp = query(1, 0, n - 1, start, n - 1);
			if (tmp.st <= 0){
				add(tmp.nd);
				update(1, 0, n - 1, tmp.nd, modulo);
				start = tmp.nd + 1;
			}
			else{
				break;
			}
		}
	};

	int cntr = 0;
	recompute();

	while(!todo.empty()){
		pii tmp = {0, *todo.begin()};
		if (!dist.empty()) tmp = *dist.rbegin();
		int start = tmp.nd;
		val[start] = cntr++;
		del(start);
		if (start >= k - 1){
			update(1, 0, n - 1, start - (k - 1), start - 1, -1);
		}
		else{
			update(1, 0, n - 1, 0, start - 1, -1);
			int to = (start - (k - 1) + n) % n;
			update(1, 0, n - 1, to, n - 1, -1);
		}

		recompute();
	}
	
}

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

/*
static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
	fileio();
	assert(scanf("%d%d%d", &n, &k, &q) == 3);
	r.resize(n);
	answer.resize(q);
	for (int i = 0; i < n; i++) {
		int value;
		assert(scanf("%d", &value) == 1);
		r[i] = value;
	}
	x.resize(q);
	y.resize(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	init(k, r);
	for (int i = 0; i < q; i++) {
		answer[i] = compare_plants(x[i], y[i]);
	}

	for (int i = 0; i < q; i++) {
		printf("%d\n", answer[i]);
	}

	fclose(stdout);

	return 0;
}*/

• 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