oj.uz

Submission #457924

# Submission time Handle Problem Language Result Execution time Memory
457924 2021-08-07T14:39:27 Z ComPhyPark Comparing Plants (IOI20_plants) C++14
44 / 100
 963 ms 12920 KB 
#include "plants.h"
#include<algorithm>
#include<queue>
using namespace std;
int n;
vector<int>fn, R, st, pp;
bool ifDebug = false;
void mst(int l, int r, int id) {
	if (l == r) {
		st[id] = R[l];
		return;
	}
	int m = (l + r) >> 1;
	mst(l, m, id << 1);
	mst(m + 1, r, id << 1 | 1);
	st[id] = min(st[id << 1], st[id << 1 | 1]);
}
void prop(int l, int r, int id) {
	if (pp[id] && l != r) {
		pp[id << 1] += pp[id];
		st[id << 1] += pp[id];
		pp[id << 1 | 1] += pp[id];
		st[id << 1 | 1] += pp[id];
	}
	pp[id] = 0;
}
void udt(int l, int r, int id, int s, int e, int x) {
	if (l > e || s > r)return;
	if (s <= l && r <= e) {
		st[id] += x;
		pp[id] += x;
		return;
	}
	prop(l, r, id);
	int m = (l + r) >> 1;
	udt(l, m, id << 1, s, e, x);
	udt(m + 1, r, id << 1 | 1, s, e, x);
	st[id] = min(st[id << 1], st[id << 1 | 1]);
}
int qry(int l, int r, int id, int s, int e) {
	if (l > e || s > r)return 999999;
	if (s <= l && r <= e)return st[id];
	prop(l, r, id);
	int m = (l + r) >> 1;
	int rst = min(qry(l, m, id << 1, s, e), qry(m + 1, r, id << 1 | 1, s, e));
	return rst;
}
int fz(int l, int r, int id, int s, int e) {
	if (l > e || s > r)return -1;
	if (l == r)return st[id] ? -1 : l;
	prop(l, r, id);
	int m = (l + r) / 2;
	if (s <= l && r <= e) {
		if (st[2 * id]) {
			return fz(m + 1, r, 2 * id + 1, s, e);
		}
		else {
			return fz(l, m, 2 * id, s, e);
		}
	}
	int a = fz(l, m, 2 * id, s, e);
	return a < 0 ? fz(m + 1, r, 2 * id + 1, s, e) : a;
}
void init(int k, vector<int> r) {
	int i, lfn = r.size(), a, s, e;
	bool ifP;
	queue<int>hb;
	n = r.size();
	R = r;
	st.resize(4 * n);
	pp.resize(4 * n);
	fn.resize(n);
	mst(0, n - 1, 1);
	for (i = 0; i < n; i++) {
		if (r[i] == 0)hb.push(i);
	}
	while (hb.size()) {
		//printf("%d\n", hb.front());
		if (fn[hb.front()]) {
			hb.pop();
			continue;
		}
		ifP = false;
		a = (hb.front() + n - 1) % n;
		if (a > k - 3) {
			if (qry(0, n - 1, 1, a - k + 2, a))ifP = true;
		}
		else {
			if (min(qry(0, n - 1, 1, 0, a), qry(0, n - 1, 1, a + n - k + 2, n - 1)))ifP = true;
		}
		if (ifP) {
			//printf("%d!!!!\n", hb.front());
			a = hb.front();
			fn[a] = lfn--;
			udt(0, n - 1, 1, a, a, n + 1);
			if (a > k - 2) {
				udt(0, n - 1, 1, a - k + 1, a, -1);
			}
			else {
				udt(0, n - 1, 1, 0, a, -1);
				udt(0, n - 1, 1, a + n - k + 1, n - 1, -1);
			}
			s = hb.front() - k + 1;
			e = hb.front() - 1;
			if (s < 0)s += n;
			if (e < 0)e += n;
			//printf("check %d~%d\n", s, e);
			if (s <= e) {
				a = fz(0, n - 1, 1, s, e);
			}
			else {
				a = fz(0, n - 1, 1, s, n - 1);
				if (a < 0) a = fz(0, n - 1, 1, 0, e);
			}
			//printf("push(%d)\n", a);
			if (a >= 0) hb.push(a);
			s = hb.front() + 1;
			e = hb.front() + k - 1;
			s %= n;
			e %= n;
			//printf("check %d~%d\n", s, e);
			if (s <= e) {
				a = fz(0, n - 1, 1, s, e);
			}
			else {
				a = fz(0, n - 1, 1, s, n - 1);
				if (a < 0)a = fz(0, n - 1, 1, 0, e);
			}
			//printf("push(%d)\n", a);
			if (a >= 0)hb.push(a);
		}
		hb.pop();
	}
}
int compare_plants(int x, int y) {
	return fn[x] < fn[y] ? -1 : 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 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 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 76 ms 3292 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 73 ms 3296 KB Output is correct
11 Correct 69 ms 3248 KB Output is correct
12 Correct 76 ms 3420 KB Output is correct
13 Correct 72 ms 3424 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 76 ms 3292 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 73 ms 3296 KB Output is correct
11 Correct 69 ms 3248 KB Output is correct
12 Correct 76 ms 3420 KB Output is correct
13 Correct 72 ms 3424 KB Output is correct
14 Correct 123 ms 3996 KB Output is correct
15 Correct 936 ms 12024 KB Output is correct
16 Correct 121 ms 4000 KB Output is correct
17 Correct 963 ms 12036 KB Output is correct
18 Correct 554 ms 12900 KB Output is correct
19 Correct 890 ms 12028 KB Output is correct
20 Correct 813 ms 12036 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 64 ms 3104 KB Output is correct
4 Correct 382 ms 12316 KB Output is correct
5 Correct 475 ms 12112 KB Output is correct
6 Correct 629 ms 12036 KB Output is correct
7 Correct 768 ms 12032 KB Output is correct
8 Correct 953 ms 12028 KB Output is correct
9 Correct 419 ms 12284 KB Output is correct
10 Correct 460 ms 11976 KB Output is correct
11 Correct 323 ms 12884 KB Output is correct
12 Correct 420 ms 12132 KB Output is correct
13 Correct 571 ms 12920 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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