oj.uz

Submission #302413

# Submission time Handle Problem Language Result Execution time Memory
302413 2020-09-18T16:29:52 Z ludo Comparing Plants (IOI20_plants) C++14
0 / 100
 10 ms 8832 KB 
#include<bits/stdc++.h>
#include "plants.h"
using namespace std;

const int LEN = 256 * 1024;

// segment tree:
int lo[2 * LEN]; // lowest value in range [ L(node), R(node) ) of the **non-negative** numbers.
int lazy[2 * LEN]; // decrement to propagate downwards.

vector<int> order;

int D(int a, int b, int n) {
	if (a < b)
		return b - a;
	else
		return (n+b) - a;
}


void propagate(int i) {
	int x = lazy[i];
	lo[i] -= x;
	lazy[i] = 0;

	if (i < LEN && x != 0) {
		lazy[2*i  ] += x;
		lazy[2*i+1] += x;
	}
}

void find_zeros(int i, vector<int> &zeros) {
	propagate(i);
	assert(lo[i] == 0);
	if (i >= LEN) {
		zeros.push_back(i - LEN);
	} else {
		if (lo[2*i] == lazy[2*i])
			find_zeros(2*i, zeros);
		if (lo[2*i+1] == lazy[2*i+1])
			find_zeros(2*i+1, zeros);
	}
}

// node i has range [L, R). Decrement [a, b) by one.
void dec(int i, int L, int R, int a, int b, vector<int> &zeros) {
	if (b <= L || a >= R) return; // outside interval.

	if (a <= L && R <= b) {
		// [L, R) \subseteq [a, b).
		if (++lazy[i] < lo[i]) return;

		// we have some zero inside this interval.
		find_zeros(i, zeros);
	} else {
		propagate(i);

		int M = (L+R) / 2;
		dec(2*i  , L, M, a, b, zeros);
		dec(2*i+1, M, R, a, b, zeros);
	}
}

void decrementInterval(int a, int b, vector<int> &zeros) {
	dec(1, 0, LEN, a, b, zeros);
}

void set_inf(int i) {
	vector<int> indices = { i + LEN };
	while (indices.back() > 1) {
		indices.push_back(indices.back() / 2);
	}

	while (!indices.empty()) {
		propagate(indices.back());
		indices.pop_back();
	}
	int node = i + LEN;
	assert(lazy[node] == 0);
	lo[node] = LEN;
	while (node > 1) {
		node /= 2;
		lo[node] = min(
			lo[node*2  ] - lazy[node*2  ],
			lo[node*2+1] - lazy[node*2+1]
		);
	}
}

void init(int k, vector<int> r) {
	int n = r.size();
	order.assign(n, -1);

	for (int i=0; i < 2*LEN; i++)
		lazy[i] = 0;

	for (int i=0; i < LEN; i++)
		lo[LEN+i] = i < n ? r[i] : LEN;

	for (int i = LEN; --i > 0; )
		lo[i] = min(lo[2*i], lo[2*i+1]);

	set<int> candidates, bigGap;

	// a candidate occurs in bigGap, if the gap to the previous one is >= k.

	for (int i=0; i<n; i++) {
		if (r[i] == 0)
			candidates.insert(i);
	}
	assert(!candidates.empty());
	int lc = *candidates.rbegin();
	for (int c : candidates) {
		if (D(lc, c, n) >= k)
			bigGap.insert(c);
		lc = c;
	}

	int ndone = 0, step = -1;
	while (ndone != n) {
		step++;
		assert(!bigGap.empty());
		ndone += bigGap.size();

		vector<int> v(bigGap.begin(), bigGap.end());
		bigGap.clear();

		vector<int> newCandidates;

		for (int i : v) {
			order[i] = step;
			set_inf(i);
		}

		for (int i : v) {
			int prev = i - k + 1;
			if (prev >= 0) {
				decrementInterval(prev, i, newCandidates);
			} else {
				decrementInterval(0, i, newCandidates);
				decrementInterval(prev + n, n, newCandidates);
			}
		}

		for (int i : newCandidates) {
			auto it = candidates.lower_bound(i);
			if (!candidates.empty()) {
				if (it == candidates.end())
					it = candidates.begin();
				int inxt = *it;
				if (D(i, inxt, n) < k) bigGap.erase(inxt);
			}

			it = candidates.insert(i).first;
			if (it == candidates.begin()) {
				it = candidates.end();
			} else {
				--it;
			}
			int iprv = *it;
			if (D(iprv, i, n) >= k) bigGap.insert(i);
		}

		for (int i : v) {
			candidates.erase(i);

			// check the gap of the next element.
			if (candidates.empty()) continue;

			auto it = candidates.lower_bound(i);
			if (it == candidates.end())
				it = candidates.begin();

			int inxt = *it, iprv;
			if (it == candidates.begin())
				iprv = *candidates.rbegin();
			else
				iprv = *(--it);

			if (D(iprv, inxt, n) >= k) bigGap.insert(inxt);
		}
	}

	return;
}

int compare_plants(int x, int y) {
	// order[x]  > order[y]: h[x]  < h[y] -> -1
	// order[x] == order[y]: h[x] == h[y] -> 0
	// order[x]  < order[y]: h[x]  > h[y] -> +1
	if (order[x] < order[y]) return +1;
	if (order[x] > order[y]) return -1;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4352 KB Output is correct
2 Correct 5 ms 4480 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Incorrect 3 ms 4352 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4352 KB Output is correct
2 Correct 3 ms 4352 KB Output is correct
3 Correct 3 ms 4480 KB Output is correct
4 Correct 3 ms 4352 KB Output is correct
5 Runtime error 9 ms 8832 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4352 KB Output is correct
2 Correct 3 ms 4352 KB Output is correct
3 Correct 3 ms 4480 KB Output is correct
4 Correct 3 ms 4352 KB Output is correct
5 Runtime error 9 ms 8832 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 8704 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4480 KB Output is correct
2 Correct 4 ms 4480 KB Output is correct
3 Incorrect 3 ms 4352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4480 KB Output is correct
2 Correct 3 ms 4352 KB Output is correct
3 Runtime error 9 ms 8704 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4352 KB Output is correct
2 Correct 5 ms 4480 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Incorrect 3 ms 4352 KB Output isn't correct
5 Halted 0 ms 0 KB -