oj.uz

Submission #412343

# Submission time Handle Problem Language Result Execution time Memory
412343 2021-05-26T17:33:29 Z atoiz Comparing Plants (IOI20_plants) C++14
19 / 100
 1622 ms 66224 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));
        // 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;
    if ((calc_dist(u, y) < k || calc_dist(y, u) < k) && init_rank[u] >= init_rank[y]) return true;
	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;
    if ((calc_dist(u, y) < k || calc_dist(y, u) < k) && init_rank[u] >= init_rank[y]) return true;
	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 24 ms 33228 KB Output is correct
2 Correct 23 ms 33256 KB Output is correct
3 Correct 23 ms 33232 KB Output is correct
4 Correct 24 ms 33228 KB Output is correct
5 Correct 23 ms 33252 KB Output is correct
6 Correct 262 ms 36072 KB Output is correct
7 Correct 503 ms 39096 KB Output is correct
8 Correct 1335 ms 66188 KB Output is correct
9 Correct 1284 ms 66048 KB Output is correct
10 Correct 1262 ms 66000 KB Output is correct
11 Correct 1192 ms 66008 KB Output is correct
12 Correct 1149 ms 66096 KB Output is correct
13 Correct 637 ms 66060 KB Output is correct
14 Correct 1622 ms 66104 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33228 KB Output is correct
2 Correct 24 ms 33252 KB Output is correct
3 Correct 22 ms 33252 KB Output is correct
4 Correct 25 ms 33244 KB Output is correct
5 Correct 24 ms 33336 KB Output is correct
6 Correct 28 ms 33496 KB Output is correct
7 Correct 126 ms 36876 KB Output is correct
8 Correct 26 ms 33412 KB Output is correct
9 Correct 29 ms 33484 KB Output is correct
10 Correct 126 ms 36984 KB Output is correct
11 Correct 94 ms 36840 KB Output is correct
12 Correct 259 ms 37116 KB Output is correct
13 Correct 123 ms 36932 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33228 KB Output is correct
2 Correct 24 ms 33252 KB Output is correct
3 Correct 22 ms 33252 KB Output is correct
4 Correct 25 ms 33244 KB Output is correct
5 Correct 24 ms 33336 KB Output is correct
6 Correct 28 ms 33496 KB Output is correct
7 Correct 126 ms 36876 KB Output is correct
8 Correct 26 ms 33412 KB Output is correct
9 Correct 29 ms 33484 KB Output is correct
10 Correct 126 ms 36984 KB Output is correct
11 Correct 94 ms 36840 KB Output is correct
12 Correct 259 ms 37116 KB Output is correct
13 Correct 123 ms 36932 KB Output is correct
14 Correct 176 ms 39184 KB Output is correct
15 Incorrect 954 ms 66036 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33348 KB Output is correct
2 Correct 23 ms 33228 KB Output is correct
3 Correct 221 ms 36380 KB Output is correct
4 Correct 1077 ms 66224 KB Output is correct
5 Correct 1145 ms 66032 KB Output is correct
6 Correct 1150 ms 66036 KB Output is correct
7 Correct 1071 ms 66032 KB Output is correct
8 Incorrect 966 ms 66032 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 27 ms 33248 KB Output is correct
3 Correct 23 ms 33236 KB Output is correct
4 Correct 25 ms 33260 KB Output is correct
5 Correct 24 ms 33260 KB Output is correct
6 Incorrect 30 ms 33356 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 33280 KB Output is correct
2 Correct 25 ms 33252 KB Output is correct
3 Correct 24 ms 33328 KB Output is correct
4 Correct 24 ms 33252 KB Output is correct
5 Correct 26 ms 33428 KB Output is correct
6 Correct 1165 ms 66036 KB Output is correct
7 Correct 1030 ms 66148 KB Output is correct
8 Correct 911 ms 66032 KB Output is correct
9 Incorrect 1044 ms 66032 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33228 KB Output is correct
2 Correct 23 ms 33256 KB Output is correct
3 Correct 23 ms 33232 KB Output is correct
4 Correct 24 ms 33228 KB Output is correct
5 Correct 23 ms 33252 KB Output is correct
6 Correct 262 ms 36072 KB Output is correct
7 Correct 503 ms 39096 KB Output is correct
8 Correct 1335 ms 66188 KB Output is correct
9 Correct 1284 ms 66048 KB Output is correct
10 Correct 1262 ms 66000 KB Output is correct
11 Correct 1192 ms 66008 KB Output is correct
12 Correct 1149 ms 66096 KB Output is correct
13 Correct 637 ms 66060 KB Output is correct
14 Correct 1622 ms 66104 KB Output is correct
15 Correct 27 ms 33228 KB Output is correct
16 Correct 24 ms 33252 KB Output is correct
17 Correct 22 ms 33252 KB Output is correct
18 Correct 25 ms 33244 KB Output is correct
19 Correct 24 ms 33336 KB Output is correct
20 Correct 28 ms 33496 KB Output is correct
21 Correct 126 ms 36876 KB Output is correct
22 Correct 26 ms 33412 KB Output is correct
23 Correct 29 ms 33484 KB Output is correct
24 Correct 126 ms 36984 KB Output is correct
25 Correct 94 ms 36840 KB Output is correct
26 Correct 259 ms 37116 KB Output is correct
27 Correct 123 ms 36932 KB Output is correct
28 Correct 176 ms 39184 KB Output is correct
29 Incorrect 954 ms 66036 KB Output isn't correct
30 Halted 0 ms 0 KB -