oj.uz

답안 #411971

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411971 2021-05-26T11:19:21 Z atoiz 식물 비교 (IOI20_plants) C++14
30 / 100
 1616 ms 100708 KB 
#include "plants.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cassert>

using namespace std;

const int N = 1 << 19, K = 19;
// 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 46 ms 66164 KB Output is correct
2 Correct 41 ms 66196 KB Output is correct
3 Correct 49 ms 66196 KB Output is correct
4 Correct 41 ms 66120 KB Output is correct
5 Correct 42 ms 66156 KB Output is correct
6 Correct 295 ms 69084 KB Output is correct
7 Correct 526 ms 72236 KB Output is correct
8 Correct 1395 ms 100528 KB Output is correct
9 Correct 1300 ms 100628 KB Output is correct
10 Correct 1310 ms 100708 KB Output is correct
11 Correct 1237 ms 100692 KB Output is correct
12 Correct 1177 ms 100664 KB Output is correct
13 Correct 656 ms 100668 KB Output is correct
14 Correct 1616 ms 100704 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 66120 KB Output is correct
2 Correct 44 ms 66244 KB Output is correct
3 Correct 44 ms 66224 KB Output is correct
4 Correct 47 ms 66244 KB Output is correct
5 Correct 44 ms 66140 KB Output is correct
6 Correct 50 ms 66396 KB Output is correct
7 Correct 185 ms 69968 KB Output is correct
8 Correct 54 ms 66244 KB Output is correct
9 Correct 50 ms 66464 KB Output is correct
10 Correct 209 ms 70076 KB Output is correct
11 Correct 160 ms 69964 KB Output is correct
12 Correct 440 ms 70088 KB Output is correct
13 Correct 186 ms 69968 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 66120 KB Output is correct
2 Correct 44 ms 66244 KB Output is correct
3 Correct 44 ms 66224 KB Output is correct
4 Correct 47 ms 66244 KB Output is correct
5 Correct 44 ms 66140 KB Output is correct
6 Correct 50 ms 66396 KB Output is correct
7 Correct 185 ms 69968 KB Output is correct
8 Correct 54 ms 66244 KB Output is correct
9 Correct 50 ms 66464 KB Output is correct
10 Correct 209 ms 70076 KB Output is correct
11 Correct 160 ms 69964 KB Output is correct
12 Correct 440 ms 70088 KB Output is correct
13 Correct 186 ms 69968 KB Output is correct
14 Correct 249 ms 72484 KB Output is correct
15 Incorrect 1117 ms 100656 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 66232 KB Output is correct
2 Correct 42 ms 66224 KB Output is correct
3 Correct 234 ms 69468 KB Output is correct
4 Correct 1081 ms 100648 KB Output is correct
5 Correct 1213 ms 100688 KB Output is correct
6 Correct 1222 ms 100700 KB Output is correct
7 Correct 1128 ms 100640 KB Output is correct
8 Incorrect 1169 ms 100652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 66244 KB Output is correct
2 Correct 42 ms 66188 KB Output is correct
3 Correct 43 ms 66160 KB Output is correct
4 Correct 49 ms 66244 KB Output is correct
5 Correct 46 ms 66200 KB Output is correct
6 Correct 59 ms 66348 KB Output is correct
7 Correct 104 ms 66988 KB Output is correct
8 Correct 67 ms 66992 KB Output is correct
9 Correct 106 ms 66884 KB Output is correct
10 Correct 68 ms 66944 KB Output is correct
11 Correct 102 ms 67004 KB Output is correct
12 Correct 90 ms 66912 KB Output is correct
13 Correct 63 ms 66984 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 66196 KB Output is correct
2 Correct 49 ms 66124 KB Output is correct
3 Correct 49 ms 66128 KB Output is correct
4 Correct 45 ms 66176 KB Output is correct
5 Correct 47 ms 66360 KB Output is correct
6 Correct 1248 ms 100656 KB Output is correct
7 Correct 1043 ms 100656 KB Output is correct
8 Correct 1018 ms 100660 KB Output is correct
9 Incorrect 1102 ms 100660 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 66164 KB Output is correct
2 Correct 41 ms 66196 KB Output is correct
3 Correct 49 ms 66196 KB Output is correct
4 Correct 41 ms 66120 KB Output is correct
5 Correct 42 ms 66156 KB Output is correct
6 Correct 295 ms 69084 KB Output is correct
7 Correct 526 ms 72236 KB Output is correct
8 Correct 1395 ms 100528 KB Output is correct
9 Correct 1300 ms 100628 KB Output is correct
10 Correct 1310 ms 100708 KB Output is correct
11 Correct 1237 ms 100692 KB Output is correct
12 Correct 1177 ms 100664 KB Output is correct
13 Correct 656 ms 100668 KB Output is correct
14 Correct 1616 ms 100704 KB Output is correct
15 Correct 47 ms 66120 KB Output is correct
16 Correct 44 ms 66244 KB Output is correct
17 Correct 44 ms 66224 KB Output is correct
18 Correct 47 ms 66244 KB Output is correct
19 Correct 44 ms 66140 KB Output is correct
20 Correct 50 ms 66396 KB Output is correct
21 Correct 185 ms 69968 KB Output is correct
22 Correct 54 ms 66244 KB Output is correct
23 Correct 50 ms 66464 KB Output is correct
24 Correct 209 ms 70076 KB Output is correct
25 Correct 160 ms 69964 KB Output is correct
26 Correct 440 ms 70088 KB Output is correct
27 Correct 186 ms 69968 KB Output is correct
28 Correct 249 ms 72484 KB Output is correct
29 Incorrect 1117 ms 100656 KB Output isn't correct
30 Halted 0 ms 0 KB -