oj.uz

답안 #411969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411969 2021-05-26T11:18:19 Z atoiz 식물 비교 (IOI20_plants) C++14
30 / 100
 1484 ms 69012 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) {
	// 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

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 33252 KB Output is correct
2 Correct 24 ms 33236 KB Output is correct
3 Correct 24 ms 33292 KB Output is correct
4 Correct 27 ms 33260 KB Output is correct
5 Correct 26 ms 33224 KB Output is correct
6 Correct 281 ms 37056 KB Output is correct
7 Correct 478 ms 41260 KB Output is correct
8 Correct 1292 ms 68936 KB Output is correct
9 Correct 1239 ms 68912 KB Output is correct
10 Correct 1242 ms 69012 KB Output is correct
11 Correct 1131 ms 68912 KB Output is correct
12 Correct 1154 ms 68924 KB Output is correct
13 Correct 651 ms 68968 KB Output is correct
14 Correct 1484 ms 68988 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 33228 KB Output is correct
2 Correct 22 ms 33252 KB Output is correct
3 Correct 25 ms 33244 KB Output is correct
4 Correct 24 ms 33252 KB Output is correct
5 Correct 23 ms 33256 KB Output is correct
6 Correct 29 ms 33580 KB Output is correct
7 Correct 194 ms 37184 KB Output is correct
8 Correct 26 ms 33328 KB Output is correct
9 Correct 29 ms 33564 KB Output is correct
10 Correct 161 ms 37232 KB Output is correct
11 Correct 139 ms 37132 KB Output is correct
12 Correct 391 ms 37364 KB Output is correct
13 Correct 152 ms 37236 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 33228 KB Output is correct
2 Correct 22 ms 33252 KB Output is correct
3 Correct 25 ms 33244 KB Output is correct
4 Correct 24 ms 33252 KB Output is correct
5 Correct 23 ms 33256 KB Output is correct
6 Correct 29 ms 33580 KB Output is correct
7 Correct 194 ms 37184 KB Output is correct
8 Correct 26 ms 33328 KB Output is correct
9 Correct 29 ms 33564 KB Output is correct
10 Correct 161 ms 37232 KB Output is correct
11 Correct 139 ms 37132 KB Output is correct
12 Correct 391 ms 37364 KB Output is correct
13 Correct 152 ms 37236 KB Output is correct
14 Correct 214 ms 39408 KB Output is correct
15 Incorrect 1026 ms 66300 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 33220 KB Output is correct
2 Correct 24 ms 33244 KB Output is correct
3 Correct 211 ms 36660 KB Output is correct
4 Correct 988 ms 66312 KB Output is correct
5 Correct 1114 ms 66320 KB Output is correct
6 Correct 1099 ms 66416 KB Output is correct
7 Correct 1088 ms 66288 KB Output is correct
8 Incorrect 1077 ms 66292 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 33228 KB Output is correct
2 Correct 24 ms 33320 KB Output is correct
3 Correct 21 ms 33252 KB Output is correct
4 Correct 21 ms 33228 KB Output is correct
5 Correct 27 ms 33260 KB Output is correct
6 Correct 29 ms 33424 KB Output is correct
7 Correct 80 ms 34244 KB Output is correct
8 Correct 45 ms 34180 KB Output is correct
9 Correct 66 ms 34196 KB Output is correct
10 Correct 45 ms 34244 KB Output is correct
11 Correct 78 ms 34180 KB Output is correct
12 Correct 67 ms 34252 KB Output is correct
13 Correct 41 ms 34224 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 33220 KB Output is correct
2 Correct 24 ms 33220 KB Output is correct
3 Correct 23 ms 33256 KB Output is correct
4 Correct 28 ms 33308 KB Output is correct
5 Correct 25 ms 33492 KB Output is correct
6 Correct 1113 ms 68252 KB Output is correct
7 Correct 1022 ms 68448 KB Output is correct
8 Correct 908 ms 68684 KB Output is correct
9 Incorrect 1061 ms 68832 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 33252 KB Output is correct
2 Correct 24 ms 33236 KB Output is correct
3 Correct 24 ms 33292 KB Output is correct
4 Correct 27 ms 33260 KB Output is correct
5 Correct 26 ms 33224 KB Output is correct
6 Correct 281 ms 37056 KB Output is correct
7 Correct 478 ms 41260 KB Output is correct
8 Correct 1292 ms 68936 KB Output is correct
9 Correct 1239 ms 68912 KB Output is correct
10 Correct 1242 ms 69012 KB Output is correct
11 Correct 1131 ms 68912 KB Output is correct
12 Correct 1154 ms 68924 KB Output is correct
13 Correct 651 ms 68968 KB Output is correct
14 Correct 1484 ms 68988 KB Output is correct
15 Correct 22 ms 33228 KB Output is correct
16 Correct 22 ms 33252 KB Output is correct
17 Correct 25 ms 33244 KB Output is correct
18 Correct 24 ms 33252 KB Output is correct
19 Correct 23 ms 33256 KB Output is correct
20 Correct 29 ms 33580 KB Output is correct
21 Correct 194 ms 37184 KB Output is correct
22 Correct 26 ms 33328 KB Output is correct
23 Correct 29 ms 33564 KB Output is correct
24 Correct 161 ms 37232 KB Output is correct
25 Correct 139 ms 37132 KB Output is correct
26 Correct 391 ms 37364 KB Output is correct
27 Correct 152 ms 37236 KB Output is correct
28 Correct 214 ms 39408 KB Output is correct
29 Incorrect 1026 ms 66300 KB Output isn't correct
30 Halted 0 ms 0 KB -