Submission #412350

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
412350	2021-05-26T17:41:02 Z	atoiz	Comparing Plants (IOI20_plants)	C++14	32 / 100	1067 ms	66312 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));
        // fprintf(stderr, "%d: %d %d\n", i, move_idx(i, -jump_lef[0][i]), move_idx(i, jump_rig[0][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) {
    if (init_rank[x] <= init_rank[y]) return false;
	// fprintf(stderr, "shorter %d %d\n", x, y);
	int u;
 
	u = x;
    if ((calc_dist(u, y) < k || calc_dist(y, u) < k) && init_rank[u] >= init_rank[y]) return true;
	for (int j = K - 1; j >= 0; --j) {
		if (jump_lef[j][u] <= calc_dist(y, u) && calc_dist(y, move_idx(u, -jump_lef[j][u]) >= k)) u = move_idx(u, -jump_lef[j][u]);
	}
    if (calc_dist(y, u) >= k) u = move_idx(u, -jump_lef[0][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;
    if ((calc_dist(u, y) < k || calc_dist(y, u) < k) && init_rank[u] >= init_rank[y]) return true;
	for (int j = K - 1; j >= 0; --j) {
		if (jump_rig[j][u] <= calc_dist(u, y) && calc_dist(move_idx(u, jump_rig[j][u]), y) >= k) u = move_idx(u, jump_rig[j][u]);
	}
    if (calc_dist(u, y) >= k) u = move_idx(u, jump_rig[0][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	33228 KB	Output is correct
2	Correct	24 ms	33228 KB	Output is correct
3	Correct	24 ms	33200 KB	Output is correct
4	Correct	24 ms	33252 KB	Output is correct
5	Correct	23 ms	33252 KB	Output is correct
6	Correct	152 ms	36116 KB	Output is correct
7	Correct	385 ms	39132 KB	Output is correct
8	Correct	975 ms	66144 KB	Output is correct
9	Correct	980 ms	66004 KB	Output is correct
10	Correct	897 ms	66160 KB	Output is correct
11	Correct	848 ms	66020 KB	Output is correct
12	Correct	859 ms	66312 KB	Output is correct
13	Correct	622 ms	66104 KB	Output is correct
14	Correct	1067 ms	66228 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	33228 KB	Output is correct
2	Correct	23 ms	33256 KB	Output is correct
3	Correct	27 ms	33212 KB	Output is correct
4	Correct	24 ms	33252 KB	Output is correct
5	Correct	27 ms	33348 KB	Output is correct
6	Correct	27 ms	33452 KB	Output is correct
7	Correct	95 ms	36984 KB	Output is correct
8	Correct	25 ms	33356 KB	Output is correct
9	Correct	27 ms	33452 KB	Output is correct
10	Correct	98 ms	36960 KB	Output is correct
11	Correct	108 ms	36932 KB	Output is correct
12	Correct	93 ms	37096 KB	Output is correct
13	Correct	101 ms	36940 KB	Output is correct

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	33228 KB	Output is correct
2	Correct	23 ms	33256 KB	Output is correct
3	Correct	27 ms	33212 KB	Output is correct
4	Correct	24 ms	33252 KB	Output is correct
5	Correct	27 ms	33348 KB	Output is correct
6	Correct	27 ms	33452 KB	Output is correct
7	Correct	95 ms	36984 KB	Output is correct
8	Correct	25 ms	33356 KB	Output is correct
9	Correct	27 ms	33452 KB	Output is correct
10	Correct	98 ms	36960 KB	Output is correct
11	Correct	108 ms	36932 KB	Output is correct
12	Correct	93 ms	37096 KB	Output is correct
13	Correct	101 ms	36940 KB	Output is correct
14	Correct	150 ms	39252 KB	Output is correct
15	Correct	883 ms	66116 KB	Output is correct
16	Correct	137 ms	39096 KB	Output is correct
17	Correct	873 ms	66076 KB	Output is correct
18	Correct	498 ms	66116 KB	Output is correct
19	Correct	499 ms	66032 KB	Output is correct
20	Correct	808 ms	66112 KB	Output is correct

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	33228 KB	Output is correct
2	Correct	26 ms	33228 KB	Output is correct
3	Correct	156 ms	36396 KB	Output is correct
4	Correct	843 ms	66092 KB	Output is correct
5	Correct	901 ms	66160 KB	Output is correct
6	Correct	935 ms	66036 KB	Output is correct
7	Correct	930 ms	66036 KB	Output is correct
8	Incorrect	872 ms	66028 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #5

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	33232 KB	Output is correct
2	Correct	24 ms	33228 KB	Output is correct
3	Correct	24 ms	33268 KB	Output is correct
4	Correct	24 ms	33240 KB	Output is correct
5	Correct	24 ms	33256 KB	Output is correct
6	Incorrect	31 ms	33308 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	33248 KB	Output is correct
2	Correct	27 ms	33324 KB	Output is correct
3	Correct	23 ms	33232 KB	Output is correct
4	Correct	23 ms	33228 KB	Output is correct
5	Correct	26 ms	33404 KB	Output is correct
6	Correct	840 ms	66108 KB	Output is correct
7	Correct	810 ms	66144 KB	Output is correct
8	Correct	920 ms	66028 KB	Output is correct
9	Incorrect	896 ms	66112 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	33228 KB	Output is correct
2	Correct	24 ms	33228 KB	Output is correct
3	Correct	24 ms	33200 KB	Output is correct
4	Correct	24 ms	33252 KB	Output is correct
5	Correct	23 ms	33252 KB	Output is correct
6	Correct	152 ms	36116 KB	Output is correct
7	Correct	385 ms	39132 KB	Output is correct
8	Correct	975 ms	66144 KB	Output is correct
9	Correct	980 ms	66004 KB	Output is correct
10	Correct	897 ms	66160 KB	Output is correct
11	Correct	848 ms	66020 KB	Output is correct
12	Correct	859 ms	66312 KB	Output is correct
13	Correct	622 ms	66104 KB	Output is correct
14	Correct	1067 ms	66228 KB	Output is correct
15	Correct	23 ms	33228 KB	Output is correct
16	Correct	23 ms	33256 KB	Output is correct
17	Correct	27 ms	33212 KB	Output is correct
18	Correct	24 ms	33252 KB	Output is correct
19	Correct	27 ms	33348 KB	Output is correct
20	Correct	27 ms	33452 KB	Output is correct
21	Correct	95 ms	36984 KB	Output is correct
22	Correct	25 ms	33356 KB	Output is correct
23	Correct	27 ms	33452 KB	Output is correct
24	Correct	98 ms	36960 KB	Output is correct
25	Correct	108 ms	36932 KB	Output is correct
26	Correct	93 ms	37096 KB	Output is correct
27	Correct	101 ms	36940 KB	Output is correct
28	Correct	150 ms	39252 KB	Output is correct
29	Correct	883 ms	66116 KB	Output is correct
30	Correct	137 ms	39096 KB	Output is correct
31	Correct	873 ms	66076 KB	Output is correct
32	Correct	498 ms	66116 KB	Output is correct
33	Correct	499 ms	66032 KB	Output is correct
34	Correct	808 ms	66112 KB	Output is correct
35	Correct	23 ms	33228 KB	Output is correct
36	Correct	26 ms	33228 KB	Output is correct
37	Correct	156 ms	36396 KB	Output is correct
38	Correct	843 ms	66092 KB	Output is correct
39	Correct	901 ms	66160 KB	Output is correct
40	Correct	935 ms	66036 KB	Output is correct
41	Correct	930 ms	66036 KB	Output is correct
42	Incorrect	872 ms	66028 KB	Output isn't correct
43	Halted	0 ms	0 KB	-