oj.uz

Submission #302526

# Submission time Handle Problem Language Result Execution time Memory
302526 2020-09-18T18:20:00 Z ludo Comparing Plants (IOI20_plants) C++14
44 / 100
 555 ms 18680 KB 
#include<bits/stdc++.h>
#include "plants.h"
using namespace std;

const int LEN = 256 * 1024;
// const int LEN = 16;

// 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);

		assert(lazy[i] == 0);
		lo[i] = min(
			lo[2*i  ] - lazy[2*i  ],
			lo[2*i+1] - lazy[2*i+1]
		);
	}
}

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;
	lo[node] = LEN;
	while (node > 1) {
		node /= 2;
		assert(lazy[node] == 0);
		lo[node] = min(
			lo[node*2  ] - lazy[node*2  ],
			lo[node*2+1] - lazy[node*2+1]
		);
	}
}


void print_tree(int n) {
	for (int i=1; i<LEN+LEN; i++)
		propagate(i);
	for (int i = LEN; i < LEN + n; i++)
		cout << lo[i] << " ";
	cout << endl;
}


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]);

	// print_tree(n);

	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;

		// cerr << "Inserting " << c << endl;
	}

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

		for (int x : bigGap)
			assert(candidates.find(x) != candidates.end());
		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);
			}
		}

		// print_tree(n);

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

			// cerr << "Inserting " << i << endl;
			it = candidates.insert(i).first;
			if (it == candidates.begin())
				it = candidates.end();
			int iprv = *(--it);
			if (D(iprv, i, n) >= k) bigGap.insert(i);
		}

		for (int i : v) {
			candidates.erase(i);
			// cerr << "Erasing " << i << endl;

			// 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(i, inxt, n) < k && D(iprv, inxt, n) >= k) bigGap.insert(inxt);
		}

		// print_tree(n);
	}

	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 3 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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4384 KB Output is correct
2 Correct 3 ms 4480 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 4 ms 4352 KB Output is correct
5 Correct 4 ms 4480 KB Output is correct
6 Correct 7 ms 4480 KB Output is correct
7 Correct 91 ms 7288 KB Output is correct
8 Correct 6 ms 4480 KB Output is correct
9 Correct 8 ms 4480 KB Output is correct
10 Correct 87 ms 7288 KB Output is correct
11 Correct 83 ms 7416 KB Output is correct
12 Correct 83 ms 7544 KB Output is correct
13 Correct 85 ms 7544 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4384 KB Output is correct
2 Correct 3 ms 4480 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 4 ms 4352 KB Output is correct
5 Correct 4 ms 4480 KB Output is correct
6 Correct 7 ms 4480 KB Output is correct
7 Correct 91 ms 7288 KB Output is correct
8 Correct 6 ms 4480 KB Output is correct
9 Correct 8 ms 4480 KB Output is correct
10 Correct 87 ms 7288 KB Output is correct
11 Correct 83 ms 7416 KB Output is correct
12 Correct 83 ms 7544 KB Output is correct
13 Correct 85 ms 7544 KB Output is correct
14 Correct 121 ms 7544 KB Output is correct
15 Correct 555 ms 9208 KB Output is correct
16 Correct 122 ms 7672 KB Output is correct
17 Correct 545 ms 9080 KB Output is correct
18 Correct 486 ms 13816 KB Output is correct
19 Correct 408 ms 9208 KB Output is correct
20 Correct 526 ms 9080 KB Output is correct

Subtask #4
17.0 / 17.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 75 ms 7384 KB Output is correct
4 Correct 396 ms 12280 KB Output is correct
5 Correct 436 ms 9976 KB Output is correct
6 Correct 509 ms 9336 KB Output is correct
7 Correct 524 ms 9208 KB Output is correct
8 Correct 534 ms 9208 KB Output is correct
9 Correct 429 ms 11512 KB Output is correct
10 Correct 410 ms 10232 KB Output is correct
11 Correct 383 ms 18680 KB Output is correct
12 Correct 353 ms 9336 KB Output is correct
13 Correct 486 ms 15736 KB Output is correct

Subtask #5
0 / 11.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 Incorrect 4 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 4352 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 #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4352 KB Output is correct
2 Correct 3 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 -