Submission #1133328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133328		alterio	Comparing Plants (IOI20_plants)	C++20	0 / 100	11 ms	19236 KiB

plants

#include <bits/stdc++.h>
#include "plants.h"

using namespace std;

#define ll long long

const int mxn = 2e5 + 100;

int n, k;
vector<int> R, vals;

struct SGT {
	vector<pair<ll, ll>> sgt;
	vector<ll> lz;

	SGT(int sz) {
		sgt.resize(4 * sz);
		lz.resize(4 * sz);
	}

	void merge(int k) {
		int ind = sgt[k * 2].second;
		if (sgt[k * 2 + 1].first < sgt[k * 2].first) ind = sgt[k * 2 + 1].second;
		sgt[k] = {min(sgt[k * 2].first, sgt[k * 2 + 1].first), ind};
	}

	void build(int k, int l, int r) {
		if (l == r) {
			sgt[k] = {R[l], l};
			return;
		}
		int mid = (l + r) / 2;
		build(k * 2, l, mid);
		build(k * 2 + 1, mid + 1, r);
		merge(k);
	}

	void push(int k, int l, int r) {
		if (lz[k]) {
			sgt[k].first += lz[k];
			if (l != r) {
				lz[k * 2] += lz[k];
				lz[k * 2 + 1] += lz[k];
			}
			lz[k] = 0;
		}
	}

	pair<ll, ll> get(int k, int l, int r, int i, int j) {
		push(k, l, r);
		if (l > j || r < i) return {1e8, 1e8};
		if (i <= l && r <= j) return sgt[k];
		int mid = (l + r) / 2;
		pair<ll, ll> ansL, ansR;
		ansL = get(k * 2, l, mid, i, j);
		ansR = get(k * 2 + 1, mid + 1, r, i, j);
		int ind = ansL.second;
		if (ansR.first < ansL.first) ind = ansR.second; 
		return {min(ansL.first, ansR.first), ind};
	}

	void updateIND(int k, int l, int r, int i, ll val) {
		push(k, l, r);
		if (l > i || r < i) return;
		if (l == r) {
			sgt[k].first = val;
			return;
		}
		int mid = (l + r) / 2;
		updateIND(k * 2, l, mid, i, val);
		updateIND(k * 2 + 1, mid + 1, r, i, val);
		merge(k);
	}

	void update(int k, int l, int r, int i, int j) {
		push(k, l, r);
		if (l > j || r < i) return;
		if (i <= l && r <= j) {
			lz[k]--;
			push(k, l, r);
			return;
		}
		int mid = (l + r) / 2;
		update(k * 2, l, mid, i, j);
		update(k * 2 + 1, mid + 1, r, i, j);
		merge(k);
	}
} sgt(mxn);

int check(int pos) {
	if (pos >= k) return sgt.get(1, 0, n - 1, pos - k, pos).second;
	int left = k - pos - 1;
	pair<ll, ll> f, s;
	f = sgt.get(1, 0, n - 1, 0, pos);
	s = sgt.get(1, 0, n - 1, n - 1 - left, n - 1);
	if (s.first <= f.first) return s.second;
	return f.second;
}

void update(int pos) {
	if (pos >= k) sgt.update(1, 0, n - 1, pos - k, pos);
	int left = k - pos - 1;
	sgt.update(1, 0, n - 1, 0, pos);
	sgt.update(1, 0, n - 1, n - 1 - left, n - 1);
}

void init(int _k, vector<int> _r) {
	R = _r;
	n = R.size();
	k = _k;
	k--;
	vals.resize(n);
	sgt.build(1, 0, n - 1);
	for (int i = 0; i < n; i++) {
		pair<ll, ll> get = sgt.get(1, 0, n - 1, 0, n - 1);
		int pos = get.second;
		set<int> s;
		while (check(pos) != pos) {
			pos = check(pos);
			if (s.count(pos)) assert(0);
			s.insert(pos);
		}
		update(pos);
		vals[pos] = n - i;
		sgt.updateIND(1, 0, n - 1, pos, 1e8);
	}
}

int compare_plants(int x, int y) {
	if (vals[x] == vals[y]) return 0;
	return (vals[x] > vals[y] ? 1 : -1);
}

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