oj.uz

Submission #411980

# Submission time Handle Problem Language Result Execution time Memory
411980 2021-05-26T11:34:20 Z atoiz Comparing Plants (IOI20_plants) C++14
45 / 100
 1556 ms 83304 KB 
#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];
bool shorter_0[N], taller_0[N];
vector<int> adj[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));
		// fprintf(stderr, "nxt %d: %d %d\n", i, move_idx(i, -jump_lef[0][i]), move_idx(i, jump_rig[0][i]));
		adj[move_idx(i, jump_rig[0][i])].push_back(i);
		adj[move_idx(i, -jump_lef[0][i])].push_back(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];
		}
	}

	vector<int> bfs = {0};
	shorter_0[0] = true;
	for (int i = 0; i < (int) bfs.size(); ++i) {
		int u = bfs[i];
		// fprintf(stderr, "shorter %d\n", u);
		for (int v : adj[u]) {
			if (shorter_0[v]) continue;
			shorter_0[v] = true;
			bfs.push_back(v);
		}
	}

	bfs = {0};
	taller_0[0] = true;
	for (int i = 0; i < (int) bfs.size(); ++i) {
		int u = bfs[i];
		// fprintf(stderr, "taller %d\n", u);
		{
			int v = move_idx(u, -jump_lef[0][u]);
			if (!taller_0[v]) {
				taller_0[v] = true;
				bfs.push_back(v);
			}
		}
		{
			int v = move_idx(u, +jump_rig[0][u]);
			if (!taller_0[v]) {
				taller_0[v] = true;
				bfs.push_back(v);
			}
		}
	}

	return;
}

bool is_shorter(int x, int y) {
	// fprintf(stderr, "shorter %d %d\n", x, y);
	if (x == y) return false;
	if (x == 0) return taller_0[y];
	if (y == 0) return shorter_0[x];
	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 24 ms 39424 KB Output is correct
2 Correct 24 ms 39484 KB Output is correct
3 Correct 26 ms 39380 KB Output is correct
4 Correct 28 ms 39364 KB Output is correct
5 Correct 26 ms 39452 KB Output is correct
6 Correct 271 ms 42600 KB Output is correct
7 Correct 482 ms 46076 KB Output is correct
8 Correct 1389 ms 78400 KB Output is correct
9 Correct 1272 ms 78648 KB Output is correct
10 Correct 1301 ms 78644 KB Output is correct
11 Correct 1182 ms 78908 KB Output is correct
12 Correct 1169 ms 79304 KB Output is correct
13 Correct 654 ms 80632 KB Output is correct
14 Correct 1556 ms 80580 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 39412 KB Output is correct
2 Correct 24 ms 39456 KB Output is correct
3 Correct 25 ms 39476 KB Output is correct
4 Correct 28 ms 39444 KB Output is correct
5 Correct 29 ms 39460 KB Output is correct
6 Correct 30 ms 39744 KB Output is correct
7 Correct 153 ms 43588 KB Output is correct
8 Correct 30 ms 39500 KB Output is correct
9 Correct 31 ms 39680 KB Output is correct
10 Correct 156 ms 43460 KB Output is correct
11 Correct 145 ms 43540 KB Output is correct
12 Correct 396 ms 43716 KB Output is correct
13 Correct 159 ms 43468 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 39412 KB Output is correct
2 Correct 24 ms 39456 KB Output is correct
3 Correct 25 ms 39476 KB Output is correct
4 Correct 28 ms 39444 KB Output is correct
5 Correct 29 ms 39460 KB Output is correct
6 Correct 30 ms 39744 KB Output is correct
7 Correct 153 ms 43588 KB Output is correct
8 Correct 30 ms 39500 KB Output is correct
9 Correct 31 ms 39680 KB Output is correct
10 Correct 156 ms 43460 KB Output is correct
11 Correct 145 ms 43540 KB Output is correct
12 Correct 396 ms 43716 KB Output is correct
13 Correct 159 ms 43468 KB Output is correct
14 Correct 221 ms 46252 KB Output is correct
15 Incorrect 1153 ms 80212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39408 KB Output is correct
2 Correct 24 ms 39408 KB Output is correct
3 Correct 210 ms 42848 KB Output is correct
4 Correct 1071 ms 79972 KB Output is correct
5 Correct 1214 ms 79840 KB Output is correct
6 Correct 1191 ms 80884 KB Output is correct
7 Correct 1189 ms 80912 KB Output is correct
8 Incorrect 1205 ms 80952 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 23 ms 39500 KB Output is correct
2 Correct 27 ms 39448 KB Output is correct
3 Correct 29 ms 39388 KB Output is correct
4 Correct 25 ms 39408 KB Output is correct
5 Correct 25 ms 39500 KB Output is correct
6 Correct 35 ms 39564 KB Output is correct
7 Correct 80 ms 40264 KB Output is correct
8 Correct 48 ms 40280 KB Output is correct
9 Correct 64 ms 40160 KB Output is correct
10 Correct 45 ms 40260 KB Output is correct
11 Correct 82 ms 40148 KB Output is correct
12 Correct 69 ms 40260 KB Output is correct
13 Correct 53 ms 40260 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 39500 KB Output is correct
2 Correct 25 ms 39484 KB Output is correct
3 Correct 28 ms 39404 KB Output is correct
4 Correct 30 ms 39432 KB Output is correct
5 Correct 28 ms 39684 KB Output is correct
6 Correct 627 ms 78724 KB Output is correct
7 Correct 834 ms 80792 KB Output is correct
8 Correct 906 ms 80920 KB Output is correct
9 Correct 936 ms 81164 KB Output is correct
10 Correct 517 ms 80744 KB Output is correct
11 Correct 737 ms 83304 KB Output is correct
12 Correct 480 ms 81732 KB Output is correct
13 Correct 617 ms 81300 KB Output is correct
14 Correct 797 ms 83016 KB Output is correct
15 Correct 887 ms 83232 KB Output is correct
16 Correct 546 ms 81840 KB Output is correct
17 Correct 588 ms 81608 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39424 KB Output is correct
2 Correct 24 ms 39484 KB Output is correct
3 Correct 26 ms 39380 KB Output is correct
4 Correct 28 ms 39364 KB Output is correct
5 Correct 26 ms 39452 KB Output is correct
6 Correct 271 ms 42600 KB Output is correct
7 Correct 482 ms 46076 KB Output is correct
8 Correct 1389 ms 78400 KB Output is correct
9 Correct 1272 ms 78648 KB Output is correct
10 Correct 1301 ms 78644 KB Output is correct
11 Correct 1182 ms 78908 KB Output is correct
12 Correct 1169 ms 79304 KB Output is correct
13 Correct 654 ms 80632 KB Output is correct
14 Correct 1556 ms 80580 KB Output is correct
15 Correct 25 ms 39412 KB Output is correct
16 Correct 24 ms 39456 KB Output is correct
17 Correct 25 ms 39476 KB Output is correct
18 Correct 28 ms 39444 KB Output is correct
19 Correct 29 ms 39460 KB Output is correct
20 Correct 30 ms 39744 KB Output is correct
21 Correct 153 ms 43588 KB Output is correct
22 Correct 30 ms 39500 KB Output is correct
23 Correct 31 ms 39680 KB Output is correct
24 Correct 156 ms 43460 KB Output is correct
25 Correct 145 ms 43540 KB Output is correct
26 Correct 396 ms 43716 KB Output is correct
27 Correct 159 ms 43468 KB Output is correct
28 Correct 221 ms 46252 KB Output is correct
29 Incorrect 1153 ms 80212 KB Output isn't correct
30 Halted 0 ms 0 KB -