oj.uz

Submission #411964

# Submission time Handle Problem Language Result Execution time Memory
411964 2021-05-26T11:13:19 Z atoiz Comparing Plants (IOI20_plants) C++14
44 / 100
 909 ms 69836 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];

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) {
	return init_rank[x] > init_rank[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]);
	}
	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]);
	}
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33228 KB Output is correct
2 Correct 21 ms 33248 KB Output is correct
3 Correct 21 ms 33368 KB Output is correct
4 Incorrect 22 ms 33224 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 22 ms 33316 KB Output is correct
2 Correct 22 ms 33228 KB Output is correct
3 Correct 23 ms 33260 KB Output is correct
4 Correct 23 ms 33300 KB Output is correct
5 Correct 22 ms 33356 KB Output is correct
6 Correct 25 ms 33492 KB Output is correct
7 Correct 94 ms 38872 KB Output is correct
8 Correct 23 ms 33348 KB Output is correct
9 Correct 26 ms 33488 KB Output is correct
10 Correct 97 ms 38884 KB Output is correct
11 Correct 88 ms 38668 KB Output is correct
12 Correct 99 ms 38980 KB Output is correct
13 Correct 95 ms 38884 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33316 KB Output is correct
2 Correct 22 ms 33228 KB Output is correct
3 Correct 23 ms 33260 KB Output is correct
4 Correct 23 ms 33300 KB Output is correct
5 Correct 22 ms 33356 KB Output is correct
6 Correct 25 ms 33492 KB Output is correct
7 Correct 94 ms 38872 KB Output is correct
8 Correct 23 ms 33348 KB Output is correct
9 Correct 26 ms 33488 KB Output is correct
10 Correct 97 ms 38884 KB Output is correct
11 Correct 88 ms 38668 KB Output is correct
12 Correct 99 ms 38980 KB Output is correct
13 Correct 95 ms 38884 KB Output is correct
14 Correct 141 ms 41456 KB Output is correct
15 Correct 849 ms 69740 KB Output is correct
16 Correct 137 ms 41344 KB Output is correct
17 Correct 909 ms 69744 KB Output is correct
18 Correct 497 ms 69580 KB Output is correct
19 Correct 485 ms 69836 KB Output is correct
20 Correct 790 ms 69812 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33356 KB Output is correct
2 Correct 22 ms 33348 KB Output is correct
3 Correct 86 ms 38220 KB Output is correct
4 Correct 441 ms 68916 KB Output is correct
5 Correct 551 ms 69172 KB Output is correct
6 Correct 767 ms 69312 KB Output is correct
7 Correct 874 ms 69556 KB Output is correct
8 Correct 849 ms 69704 KB Output is correct
9 Correct 488 ms 69076 KB Output is correct
10 Correct 499 ms 69052 KB Output is correct
11 Correct 400 ms 68944 KB Output is correct
12 Correct 470 ms 69296 KB Output is correct
13 Correct 529 ms 69264 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33228 KB Output is correct
2 Correct 22 ms 33280 KB Output is correct
3 Incorrect 21 ms 33248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33228 KB Output is correct
2 Correct 21 ms 33248 KB Output is correct
3 Correct 21 ms 33368 KB Output is correct
4 Incorrect 22 ms 33224 KB Output isn't correct
5 Halted 0 ms 0 KB -