Submission #411969

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
411969	2021-05-26T11:18:19 Z	atoiz	Comparing Plants (IOI20_plants)	C++14	30 / 100	1484 ms	69012 KB

plants

#include "plants.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cassert>

using namespace std;

const int N = 1 << 18, K = 18;
// const int K = 6, N = 1 << K;

struct min_val_t {
	struct node_t {
		int pos, val, inc;
		node_t(int _pos = 0, int _val = 0, int _inc = 0): pos(_pos), val(_val), inc(_inc) {}
	} a[N << 2];
	int n;

	void pull(int rt) {
		int lc = rt << 1, rc = lc | 1;
		a[rt].pos = (a[lc].val < a[rc].val) ? a[lc].pos : a[rc].pos;
		a[rt].val = min(a[lc].val, a[rc].val) + a[rt].inc;
	}

	void build(int rt, int lo, int hi, vector<int> &r) {
		if (lo == hi) {
			a[rt] = {lo, r[lo], 0}; 
		} else {
			int lc = rt << 1, rc = lc | 1, md = (lo + hi) >> 1;
			build(lc, lo, md, r);
			build(rc, md + 1, hi, r);
			a[rt].inc = 0;
			pull(rt);
		}
	}

	int get_val() { return a[1].val; }
	int get_pos() { return a[1].pos; }

	void modify(int rt, int lo, int hi, int l, int r, int x) {
		if (r < lo || hi < l) return;
		if (l <= lo && hi <= r) {
			a[rt].val += x, a[rt].inc += x;
			return;
		}

		int lc = rt << 1, rc = lc | 1, md = (lo + hi) >> 1;
		modify(lc, lo, md, l, r, x);
		modify(rc, md + 1, hi, l, r, x);
		pull(rt);
	}

	void modify(int l, int r, int x) {
		modify(1, 0, n - 1, l, r, x);
	}

	min_val_t(vector<int> r) {
		// fprintf(stderr, "%s\n", "OK");
		n = (int) r.size();
		build(1, 0, n - 1, r);
	}
};

struct max_dist_t {
	struct node_t {
		int pos, lef, rig, len, best_pos, best_dist;
		node_t(int _pos = -1, int _lef = -1, int _rig = -1, int _len = 0, int _best_pos = -1, int _best_dist = -1):
			pos(_pos), lef(_lef), rig(_rig), len(_len), best_pos(_best_pos), best_dist(_best_dist) {}

		void on(int p) {
			pos = p, lef = 0, rig = 0, len = 1, best_pos = -1, best_dist = -1;
		}

		void off(int p) {
			pos = -1, lef = -1, rig = -1, len = 1, best_pos = -1, best_dist = -1;	
		}

		friend node_t operator+ (node_t l, node_t r) {
			node_t x;
			if (l.pos == -1) x = r, x.lef += l.len, x.len += l.len;
			else if (r.pos == -1) x = l, x.rig += r.len, x.len += r.len;
			else {
				x.pos = l.pos;
				x.lef = l.lef;
				x.rig = r.rig;
				x.len = l.len + r.len;
				if (l.best_dist > r.best_dist) {
					x.best_pos = l.best_pos;
					x.best_dist = l.best_dist;
				} else {
					x.best_pos = r.best_pos;
					x.best_dist = r.best_dist;
				}
				if (l.rig + r.lef > x.best_dist) {
					x.best_pos = r.pos;
					x.best_dist = l.rig + r.lef;
				}
			}
			return x;
		}
	} a[N << 1];
	int n;

	max_dist_t(int _n) {
		n = _n;
		for (int i = 0; i < N; ++i) a[N + i].off(i);
		for (int i = n; i < N; ++i) a[N + i].len = 0;
		for (int i = N - 1; i > 0; --i) a[i] = a[i << 1] + a[i << 1 | 1];
	}

	void turn_on(int i) {
		a[i + N].on(i);
		for (i = (i + N) / 2; i > 0; i >>= 1) a[i] = a[i << 1] + a[i << 1 | 1];
	}

	void turn_off(int i) {
		a[i + N].off(i);
		for (i = (i + N) / 2; i > 0; i >>= 1) a[i] = a[i << 1] + a[i << 1 | 1];
	}
	
	int get() {
		int pos = a[1].best_pos;
		// cout << "S" << a[1].pos << endl;
		if (a[1].lef + a[1].rig > a[1].best_dist) pos = a[1].pos;
		assert(pos != -1);
		return pos;
	}
};

struct assign_t {
	int n, a[N << 2];

	void build(int rt, int lo, int hi) {
		if (lo == hi) {
			a[rt] = lo;
		} else {
			a[rt] = -1;
			int lc = rt << 1, rc = lc | 1, md = (lo + hi) >> 1;
			build(lc, lo, md);
			build(rc, md + 1, hi);
		}
	}

	assign_t(int _n) {
		n = _n;
		build(1, 0, n - 1);
	}

	void modify(int rt, int lo, int hi, int l, int r, int x) {
		if (r < lo || hi < l) return;
		if (l <= lo && hi <= r) return a[rt] = x, void(0);

		int lc = rt << 1, rc = lc | 1, md = (lo + hi) >> 1;
		if (a[rt] != -1) a[lc] = a[rc] = a[rt], a[rt] = -1;
		modify(lc, lo, md, l, r, x);
		modify(rc, md + 1, hi, l, r, x);
	}
	void modify(int l, int r, int x) {
		l = max(0, l), r = min(n - 1, r);
		if (l <= r) modify(1, 0, n - 1, l, r, x);
	}

	int get(int i) {
		int rt = 1, lo = 0, hi = n - 1;
		while (a[rt] == -1) {
			int md = (lo + hi) >> 1;
			if (i <= md) rt = rt << 1, hi = md;
			else rt = rt << 1 | 1, lo = md + 1;
		}
		return a[rt];
	}
};

int n, k, init_rank[N], jump_lef[K][N], jump_rig[K][N];

int calc_dist(int l, int r) {
	int d = r - l;
	if (d < 0) d += n;
	return d;
}

int move_idx(int i, int d) {
	return (((i + d) % n) + n) % n;
}

void init(int _k, vector<int> a) {
	// for (int x : a) cout << x << ' '; cout << endl;
	n = (int) a.size(), k = _k;
	min_val_t min_val_query(a);
	max_dist_t max_dist_query(n);
	assign_t assign_left_query(n), assign_right_query(n);

	for (int rnk = 0; rnk < n; ++rnk) {
		while (min_val_query.get_val() == 0) {
			int i = min_val_query.get_pos();
			max_dist_query.turn_on(i);
			min_val_query.modify(i, i, N);
		}

		int i = max_dist_query.get();
		min_val_query.modify(i - k + 1, i, -1);
		min_val_query.modify(i + n - k + 1, n - 1, -1);
		max_dist_query.turn_off(i);

		init_rank[i] = rnk;
		jump_lef[0][i] = calc_dist(assign_left_query.get(i), i);
		jump_rig[0][i] = calc_dist(i, assign_right_query.get(i));

		assign_right_query.modify(i - k + 1, i, i);
		assign_right_query.modify(i + n - k + 1, n - 1, i);

		assign_left_query.modify(i, i + k - 1, i);
		assign_left_query.modify(0, i - n + k - 1, i);
	}

	for (int j = 1; j < K; ++j) {
		for (int u = 0; u < n; ++u) {
			int v;

			v = move_idx(u, -jump_lef[j - 1][u]);
			jump_lef[j][u] = jump_lef[j - 1][u] + jump_lef[j - 1][v];

			v = move_idx(u, jump_rig[j - 1][u]);
			jump_rig[j][u] = jump_rig[j - 1][u] + jump_rig[j - 1][v];
		}
	}

	return;
}

bool is_shorter(int x, int y) {
	// fprintf(stderr, "shorter %d %d\n", x, y);
	if (x == y) return false;
	int u;

	u = x;
	for (int j = K - 1; j >= 0; --j) {
		if (jump_lef[j][u] <= calc_dist(y, u)) u = move_idx(u, -jump_lef[j][u]);
	}
	// fprintf(stderr, "u = %d\n", u);
	if ((calc_dist(u, y) < k || calc_dist(y, u) < k) && init_rank[u] >= init_rank[y]) return true;

	u = x;
	for (int j = K - 1; j >= 0; --j) {
		if (jump_rig[j][u] <= calc_dist(u, y)) u = move_idx(u, jump_rig[j][u]);
	}
	// fprintf(stderr, "u = %d\n", u);
	if ((calc_dist(u, y) < k || calc_dist(y, u) < k) && init_rank[u] >= init_rank[y]) return true;

	return false;
}

int compare_plants(int x, int y) {
	if (is_shorter(y, x)) return 1;
	if (is_shorter(x, y)) return -1;
	return 0;
}

// int main() {
	// vector<int> r = {0, 1, 4, 2, 3, 6, 7, 5};
	// min_val_t mv(r);
	// for (int k = 0; k < 8; ++k) {
	// 	cout << mv.get_pos() << ": " << mv.get_val() << endl;
	// 	mv.modify(mv.get_pos(), mv.get_pos(), N * 2);
	// 	mv.modify(0, 7, -1);
	// }

	// max_dist_t md(8);
	// // md.turn_on(5);
	// // md.turn_on(0);
	// cout << md.get() << endl;

	// assign_t a(8);
	// cout << a.get(3) << endl;
	// a.modify(1, 4, 2);
	// cout << a.get(3) << endl;
	// a.modify(1, 1, 3);
	// cout << a.get(3) << endl;
// }

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	33252 KB	Output is correct
2	Correct	24 ms	33236 KB	Output is correct
3	Correct	24 ms	33292 KB	Output is correct
4	Correct	27 ms	33260 KB	Output is correct
5	Correct	26 ms	33224 KB	Output is correct
6	Correct	281 ms	37056 KB	Output is correct
7	Correct	478 ms	41260 KB	Output is correct
8	Correct	1292 ms	68936 KB	Output is correct
9	Correct	1239 ms	68912 KB	Output is correct
10	Correct	1242 ms	69012 KB	Output is correct
11	Correct	1131 ms	68912 KB	Output is correct
12	Correct	1154 ms	68924 KB	Output is correct
13	Correct	651 ms	68968 KB	Output is correct
14	Correct	1484 ms	68988 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	33228 KB	Output is correct
2	Correct	22 ms	33252 KB	Output is correct
3	Correct	25 ms	33244 KB	Output is correct
4	Correct	24 ms	33252 KB	Output is correct
5	Correct	23 ms	33256 KB	Output is correct
6	Correct	29 ms	33580 KB	Output is correct
7	Correct	194 ms	37184 KB	Output is correct
8	Correct	26 ms	33328 KB	Output is correct
9	Correct	29 ms	33564 KB	Output is correct
10	Correct	161 ms	37232 KB	Output is correct
11	Correct	139 ms	37132 KB	Output is correct
12	Correct	391 ms	37364 KB	Output is correct
13	Correct	152 ms	37236 KB	Output is correct

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	33228 KB	Output is correct
2	Correct	22 ms	33252 KB	Output is correct
3	Correct	25 ms	33244 KB	Output is correct
4	Correct	24 ms	33252 KB	Output is correct
5	Correct	23 ms	33256 KB	Output is correct
6	Correct	29 ms	33580 KB	Output is correct
7	Correct	194 ms	37184 KB	Output is correct
8	Correct	26 ms	33328 KB	Output is correct
9	Correct	29 ms	33564 KB	Output is correct
10	Correct	161 ms	37232 KB	Output is correct
11	Correct	139 ms	37132 KB	Output is correct
12	Correct	391 ms	37364 KB	Output is correct
13	Correct	152 ms	37236 KB	Output is correct
14	Correct	214 ms	39408 KB	Output is correct
15	Incorrect	1026 ms	66300 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	33220 KB	Output is correct
2	Correct	24 ms	33244 KB	Output is correct
3	Correct	211 ms	36660 KB	Output is correct
4	Correct	988 ms	66312 KB	Output is correct
5	Correct	1114 ms	66320 KB	Output is correct
6	Correct	1099 ms	66416 KB	Output is correct
7	Correct	1088 ms	66288 KB	Output is correct
8	Incorrect	1077 ms	66292 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #5

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	33228 KB	Output is correct
2	Correct	24 ms	33320 KB	Output is correct
3	Correct	21 ms	33252 KB	Output is correct
4	Correct	21 ms	33228 KB	Output is correct
5	Correct	27 ms	33260 KB	Output is correct
6	Correct	29 ms	33424 KB	Output is correct
7	Correct	80 ms	34244 KB	Output is correct
8	Correct	45 ms	34180 KB	Output is correct
9	Correct	66 ms	34196 KB	Output is correct
10	Correct	45 ms	34244 KB	Output is correct
11	Correct	78 ms	34180 KB	Output is correct
12	Correct	67 ms	34252 KB	Output is correct
13	Correct	41 ms	34224 KB	Output is correct

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	33220 KB	Output is correct
2	Correct	24 ms	33220 KB	Output is correct
3	Correct	23 ms	33256 KB	Output is correct
4	Correct	28 ms	33308 KB	Output is correct
5	Correct	25 ms	33492 KB	Output is correct
6	Correct	1113 ms	68252 KB	Output is correct
7	Correct	1022 ms	68448 KB	Output is correct
8	Correct	908 ms	68684 KB	Output is correct
9	Incorrect	1061 ms	68832 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	33252 KB	Output is correct
2	Correct	24 ms	33236 KB	Output is correct
3	Correct	24 ms	33292 KB	Output is correct
4	Correct	27 ms	33260 KB	Output is correct
5	Correct	26 ms	33224 KB	Output is correct
6	Correct	281 ms	37056 KB	Output is correct
7	Correct	478 ms	41260 KB	Output is correct
8	Correct	1292 ms	68936 KB	Output is correct
9	Correct	1239 ms	68912 KB	Output is correct
10	Correct	1242 ms	69012 KB	Output is correct
11	Correct	1131 ms	68912 KB	Output is correct
12	Correct	1154 ms	68924 KB	Output is correct
13	Correct	651 ms	68968 KB	Output is correct
14	Correct	1484 ms	68988 KB	Output is correct
15	Correct	22 ms	33228 KB	Output is correct
16	Correct	22 ms	33252 KB	Output is correct
17	Correct	25 ms	33244 KB	Output is correct
18	Correct	24 ms	33252 KB	Output is correct
19	Correct	23 ms	33256 KB	Output is correct
20	Correct	29 ms	33580 KB	Output is correct
21	Correct	194 ms	37184 KB	Output is correct
22	Correct	26 ms	33328 KB	Output is correct
23	Correct	29 ms	33564 KB	Output is correct
24	Correct	161 ms	37232 KB	Output is correct
25	Correct	139 ms	37132 KB	Output is correct
26	Correct	391 ms	37364 KB	Output is correct
27	Correct	152 ms	37236 KB	Output is correct
28	Correct	214 ms	39408 KB	Output is correct
29	Incorrect	1026 ms	66300 KB	Output isn't correct
30	Halted	0 ms	0 KB	-