Submission #412340

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
412340	2021-05-26T17:31:58 Z	atoiz	Comparing Plants (IOI20_plants)	C++14	19 / 100	1603 ms	69900 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) {
	// 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) && 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;
	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	23 ms	33316 KB	Output is correct
2	Correct	23 ms	33256 KB	Output is correct
3	Correct	23 ms	33332 KB	Output is correct
4	Correct	24 ms	33256 KB	Output is correct
5	Correct	23 ms	33296 KB	Output is correct
6	Correct	308 ms	36084 KB	Output is correct
7	Correct	508 ms	41260 KB	Output is correct
8	Correct	1366 ms	69100 KB	Output is correct
9	Correct	1327 ms	68952 KB	Output is correct
10	Correct	1288 ms	69020 KB	Output is correct
11	Correct	1260 ms	68980 KB	Output is correct
12	Correct	1209 ms	69016 KB	Output is correct
13	Correct	601 ms	69044 KB	Output is correct
14	Correct	1603 ms	69000 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	33252 KB	Output is correct
2	Correct	25 ms	33248 KB	Output is correct
3	Correct	24 ms	33228 KB	Output is correct
4	Correct	27 ms	33292 KB	Output is correct
5	Correct	27 ms	33228 KB	Output is correct
6	Correct	33 ms	33552 KB	Output is correct
7	Correct	149 ms	36972 KB	Output is correct
8	Correct	32 ms	33348 KB	Output is correct
9	Correct	31 ms	33484 KB	Output is correct
10	Correct	178 ms	37004 KB	Output is correct
11	Correct	132 ms	36780 KB	Output is correct
12	Correct	408 ms	37064 KB	Output is correct
13	Correct	149 ms	36972 KB	Output is correct

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	33252 KB	Output is correct
2	Correct	25 ms	33248 KB	Output is correct
3	Correct	24 ms	33228 KB	Output is correct
4	Correct	27 ms	33292 KB	Output is correct
5	Correct	27 ms	33228 KB	Output is correct
6	Correct	33 ms	33552 KB	Output is correct
7	Correct	149 ms	36972 KB	Output is correct
8	Correct	32 ms	33348 KB	Output is correct
9	Correct	31 ms	33484 KB	Output is correct
10	Correct	178 ms	37004 KB	Output is correct
11	Correct	132 ms	36780 KB	Output is correct
12	Correct	408 ms	37064 KB	Output is correct
13	Correct	149 ms	36972 KB	Output is correct
14	Correct	217 ms	39188 KB	Output is correct
15	Incorrect	1129 ms	66124 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	33228 KB	Output is correct
2	Correct	25 ms	33252 KB	Output is correct
3	Correct	222 ms	36448 KB	Output is correct
4	Correct	1114 ms	68912 KB	Output is correct
5	Correct	1230 ms	69124 KB	Output is correct
6	Correct	1211 ms	69316 KB	Output is correct
7	Correct	1110 ms	69520 KB	Output is correct
8	Incorrect	1156 ms	69900 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #5

0 / 11.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	23 ms	33300 KB	Output is correct
4	Correct	23 ms	33348 KB	Output is correct
5	Correct	24 ms	33248 KB	Output is correct
6	Incorrect	29 ms	33328 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	33248 KB	Output is correct
2	Correct	24 ms	33316 KB	Output is correct
3	Correct	25 ms	33268 KB	Output is correct
4	Correct	28 ms	33228 KB	Output is correct
5	Correct	26 ms	33476 KB	Output is correct
6	Correct	1156 ms	68256 KB	Output is correct
7	Correct	1051 ms	68456 KB	Output is correct
8	Correct	958 ms	68680 KB	Output is correct
9	Incorrect	1097 ms	68844 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	33316 KB	Output is correct
2	Correct	23 ms	33256 KB	Output is correct
3	Correct	23 ms	33332 KB	Output is correct
4	Correct	24 ms	33256 KB	Output is correct
5	Correct	23 ms	33296 KB	Output is correct
6	Correct	308 ms	36084 KB	Output is correct
7	Correct	508 ms	41260 KB	Output is correct
8	Correct	1366 ms	69100 KB	Output is correct
9	Correct	1327 ms	68952 KB	Output is correct
10	Correct	1288 ms	69020 KB	Output is correct
11	Correct	1260 ms	68980 KB	Output is correct
12	Correct	1209 ms	69016 KB	Output is correct
13	Correct	601 ms	69044 KB	Output is correct
14	Correct	1603 ms	69000 KB	Output is correct
15	Correct	26 ms	33252 KB	Output is correct
16	Correct	25 ms	33248 KB	Output is correct
17	Correct	24 ms	33228 KB	Output is correct
18	Correct	27 ms	33292 KB	Output is correct
19	Correct	27 ms	33228 KB	Output is correct
20	Correct	33 ms	33552 KB	Output is correct
21	Correct	149 ms	36972 KB	Output is correct
22	Correct	32 ms	33348 KB	Output is correct
23	Correct	31 ms	33484 KB	Output is correct
24	Correct	178 ms	37004 KB	Output is correct
25	Correct	132 ms	36780 KB	Output is correct
26	Correct	408 ms	37064 KB	Output is correct
27	Correct	149 ms	36972 KB	Output is correct
28	Correct	217 ms	39188 KB	Output is correct
29	Incorrect	1129 ms	66124 KB	Output isn't correct
30	Halted	0 ms	0 KB	-