Submission #412117

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
412117	2021-05-26T14:15:11 Z	atoiz	Comparing Plants (IOI20_plants)	C++14	30 / 100	1547 ms	69712 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)) 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	22 ms	33248 KB	Output is correct
2	Correct	25 ms	33320 KB	Output is correct
3	Correct	26 ms	33276 KB	Output is correct
4	Correct	22 ms	33256 KB	Output is correct
5	Correct	26 ms	33256 KB	Output is correct
6	Correct	282 ms	37076 KB	Output is correct
7	Correct	506 ms	41232 KB	Output is correct
8	Correct	1354 ms	68920 KB	Output is correct
9	Correct	1284 ms	68908 KB	Output is correct
10	Correct	1259 ms	69024 KB	Output is correct
11	Correct	1176 ms	68916 KB	Output is correct
12	Correct	1178 ms	69016 KB	Output is correct
13	Correct	627 ms	68944 KB	Output is correct
14	Correct	1547 ms	68920 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	33228 KB	Output is correct
2	Correct	22 ms	33260 KB	Output is correct
3	Correct	24 ms	33272 KB	Output is correct
4	Correct	23 ms	33356 KB	Output is correct
5	Correct	24 ms	33336 KB	Output is correct
6	Correct	28 ms	33508 KB	Output is correct
7	Correct	158 ms	37700 KB	Output is correct
8	Correct	26 ms	33456 KB	Output is correct
9	Correct	30 ms	33580 KB	Output is correct
10	Correct	171 ms	37700 KB	Output is correct
11	Correct	172 ms	37552 KB	Output is correct
12	Correct	385 ms	37764 KB	Output is correct
13	Correct	157 ms	37700 KB	Output is correct

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	33228 KB	Output is correct
2	Correct	22 ms	33260 KB	Output is correct
3	Correct	24 ms	33272 KB	Output is correct
4	Correct	23 ms	33356 KB	Output is correct
5	Correct	24 ms	33336 KB	Output is correct
6	Correct	28 ms	33508 KB	Output is correct
7	Correct	158 ms	37700 KB	Output is correct
8	Correct	26 ms	33456 KB	Output is correct
9	Correct	30 ms	33580 KB	Output is correct
10	Correct	171 ms	37700 KB	Output is correct
11	Correct	172 ms	37552 KB	Output is correct
12	Correct	385 ms	37764 KB	Output is correct
13	Correct	157 ms	37700 KB	Output is correct
14	Correct	215 ms	39892 KB	Output is correct
15	Incorrect	1031 ms	67952 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	33228 KB	Output is correct
2	Correct	23 ms	33344 KB	Output is correct
3	Correct	215 ms	37160 KB	Output is correct
4	Correct	1095 ms	69064 KB	Output is correct
5	Correct	1077 ms	69172 KB	Output is correct
6	Correct	1127 ms	69312 KB	Output is correct
7	Correct	1057 ms	69672 KB	Output is correct
8	Incorrect	1109 ms	69712 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	33352 KB	Output is correct
2	Correct	22 ms	33264 KB	Output is correct
3	Correct	22 ms	33256 KB	Output is correct
4	Correct	23 ms	33272 KB	Output is correct
5	Correct	23 ms	33292 KB	Output is correct
6	Correct	29 ms	33420 KB	Output is correct
7	Correct	81 ms	34184 KB	Output is correct
8	Correct	55 ms	34244 KB	Output is correct
9	Correct	78 ms	34184 KB	Output is correct
10	Correct	46 ms	34260 KB	Output is correct
11	Correct	81 ms	34192 KB	Output is correct
12	Correct	68 ms	34188 KB	Output is correct
13	Correct	46 ms	34220 KB	Output is correct

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	33220 KB	Output is correct
2	Correct	23 ms	33220 KB	Output is correct
3	Correct	23 ms	33260 KB	Output is correct
4	Correct	24 ms	33260 KB	Output is correct
5	Correct	30 ms	33452 KB	Output is correct
6	Correct	1107 ms	68336 KB	Output is correct
7	Correct	1000 ms	68480 KB	Output is correct
8	Correct	890 ms	68812 KB	Output is correct
9	Incorrect	1036 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	22 ms	33248 KB	Output is correct
2	Correct	25 ms	33320 KB	Output is correct
3	Correct	26 ms	33276 KB	Output is correct
4	Correct	22 ms	33256 KB	Output is correct
5	Correct	26 ms	33256 KB	Output is correct
6	Correct	282 ms	37076 KB	Output is correct
7	Correct	506 ms	41232 KB	Output is correct
8	Correct	1354 ms	68920 KB	Output is correct
9	Correct	1284 ms	68908 KB	Output is correct
10	Correct	1259 ms	69024 KB	Output is correct
11	Correct	1176 ms	68916 KB	Output is correct
12	Correct	1178 ms	69016 KB	Output is correct
13	Correct	627 ms	68944 KB	Output is correct
14	Correct	1547 ms	68920 KB	Output is correct
15	Correct	21 ms	33228 KB	Output is correct
16	Correct	22 ms	33260 KB	Output is correct
17	Correct	24 ms	33272 KB	Output is correct
18	Correct	23 ms	33356 KB	Output is correct
19	Correct	24 ms	33336 KB	Output is correct
20	Correct	28 ms	33508 KB	Output is correct
21	Correct	158 ms	37700 KB	Output is correct
22	Correct	26 ms	33456 KB	Output is correct
23	Correct	30 ms	33580 KB	Output is correct
24	Correct	171 ms	37700 KB	Output is correct
25	Correct	172 ms	37552 KB	Output is correct
26	Correct	385 ms	37764 KB	Output is correct
27	Correct	157 ms	37700 KB	Output is correct
28	Correct	215 ms	39892 KB	Output is correct
29	Incorrect	1031 ms	67952 KB	Output isn't correct
30	Halted	0 ms	0 KB	-