oj.uz

답안 #412351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
412351 2021-05-26T17:43:22 Z atoiz 식물 비교 (IOI20_plants) C++14
30 / 100
 1043 ms 66156 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 (init_rank[x] <= init_rank[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 26 ms 33252 KB Output is correct
2 Correct 23 ms 33312 KB Output is correct
3 Correct 23 ms 33256 KB Output is correct
4 Correct 23 ms 33252 KB Output is correct
5 Correct 23 ms 33312 KB Output is correct
6 Correct 173 ms 36188 KB Output is correct
7 Correct 337 ms 39096 KB Output is correct
8 Correct 977 ms 66080 KB Output is correct
9 Correct 898 ms 66008 KB Output is correct
10 Correct 880 ms 66044 KB Output is correct
11 Correct 846 ms 66052 KB Output is correct
12 Correct 833 ms 66088 KB Output is correct
13 Correct 616 ms 66092 KB Output is correct
14 Correct 1043 ms 66000 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 33228 KB Output is correct
2 Correct 24 ms 33252 KB Output is correct
3 Correct 24 ms 33220 KB Output is correct
4 Correct 24 ms 33248 KB Output is correct
5 Correct 28 ms 33260 KB Output is correct
6 Correct 27 ms 33452 KB Output is correct
7 Correct 116 ms 36980 KB Output is correct
8 Correct 29 ms 33308 KB Output is correct
9 Correct 31 ms 33460 KB Output is correct
10 Correct 121 ms 36980 KB Output is correct
11 Correct 129 ms 36876 KB Output is correct
12 Correct 236 ms 37108 KB Output is correct
13 Correct 113 ms 36984 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 33228 KB Output is correct
2 Correct 24 ms 33252 KB Output is correct
3 Correct 24 ms 33220 KB Output is correct
4 Correct 24 ms 33248 KB Output is correct
5 Correct 28 ms 33260 KB Output is correct
6 Correct 27 ms 33452 KB Output is correct
7 Correct 116 ms 36980 KB Output is correct
8 Correct 29 ms 33308 KB Output is correct
9 Correct 31 ms 33460 KB Output is correct
10 Correct 121 ms 36980 KB Output is correct
11 Correct 129 ms 36876 KB Output is correct
12 Correct 236 ms 37108 KB Output is correct
13 Correct 113 ms 36984 KB Output is correct
14 Correct 171 ms 39092 KB Output is correct
15 Incorrect 997 ms 66032 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 33228 KB Output is correct
2 Correct 23 ms 33256 KB Output is correct
3 Correct 155 ms 36396 KB Output is correct
4 Correct 778 ms 66108 KB Output is correct
5 Correct 854 ms 66004 KB Output is correct
6 Correct 925 ms 66112 KB Output is correct
7 Correct 947 ms 66036 KB Output is correct
8 Incorrect 1006 ms 66032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 33228 KB Output is correct
2 Correct 25 ms 33308 KB Output is correct
3 Correct 24 ms 33292 KB Output is correct
4 Correct 25 ms 33316 KB Output is correct
5 Correct 25 ms 33320 KB Output is correct
6 Correct 29 ms 33440 KB Output is correct
7 Correct 61 ms 34220 KB Output is correct
8 Correct 40 ms 34252 KB Output is correct
9 Correct 56 ms 34224 KB Output is correct
10 Correct 40 ms 34296 KB Output is correct
11 Correct 56 ms 34232 KB Output is correct
12 Correct 52 ms 34184 KB Output is correct
13 Correct 40 ms 34204 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 33236 KB Output is correct
2 Correct 23 ms 33220 KB Output is correct
3 Correct 23 ms 33220 KB Output is correct
4 Correct 24 ms 33216 KB Output is correct
5 Correct 26 ms 33480 KB Output is correct
6 Correct 791 ms 66032 KB Output is correct
7 Correct 790 ms 66156 KB Output is correct
8 Correct 929 ms 66032 KB Output is correct
9 Incorrect 894 ms 66108 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 33252 KB Output is correct
2 Correct 23 ms 33312 KB Output is correct
3 Correct 23 ms 33256 KB Output is correct
4 Correct 23 ms 33252 KB Output is correct
5 Correct 23 ms 33312 KB Output is correct
6 Correct 173 ms 36188 KB Output is correct
7 Correct 337 ms 39096 KB Output is correct
8 Correct 977 ms 66080 KB Output is correct
9 Correct 898 ms 66008 KB Output is correct
10 Correct 880 ms 66044 KB Output is correct
11 Correct 846 ms 66052 KB Output is correct
12 Correct 833 ms 66088 KB Output is correct
13 Correct 616 ms 66092 KB Output is correct
14 Correct 1043 ms 66000 KB Output is correct
15 Correct 23 ms 33228 KB Output is correct
16 Correct 24 ms 33252 KB Output is correct
17 Correct 24 ms 33220 KB Output is correct
18 Correct 24 ms 33248 KB Output is correct
19 Correct 28 ms 33260 KB Output is correct
20 Correct 27 ms 33452 KB Output is correct
21 Correct 116 ms 36980 KB Output is correct
22 Correct 29 ms 33308 KB Output is correct
23 Correct 31 ms 33460 KB Output is correct
24 Correct 121 ms 36980 KB Output is correct
25 Correct 129 ms 36876 KB Output is correct
26 Correct 236 ms 37108 KB Output is correct
27 Correct 113 ms 36984 KB Output is correct
28 Correct 171 ms 39092 KB Output is correct
29 Incorrect 997 ms 66032 KB Output isn't correct
30 Halted 0 ms 0 KB -