oj.uz

Submission #412352

# Submission time Handle Problem Language Result Execution time Memory
412352 2021-05-26T17:45:10 Z atoiz Comparing Plants (IOI20_plants) C++14
14 / 100
 897 ms 132292 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) {
    if (init_rank[x] == init_rank[y]) return false;
    assert(calc_dist(x, y) < k || calc_dist(y, x) < k);
	// fprintf(stderr, "shorter %d %d\n", x, y);
	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]);
    assert(init_rank[u] <= init_rank[x]);
	// 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]);
    assert(init_rank[u] <= init_rank[x]);
	// 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33236 KB Output is correct
2 Correct 24 ms 33320 KB Output is correct
3 Correct 24 ms 33244 KB Output is correct
4 Runtime error 65 ms 67292 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33240 KB Output is correct
2 Correct 26 ms 33244 KB Output is correct
3 Correct 24 ms 33276 KB Output is correct
4 Correct 28 ms 33252 KB Output is correct
5 Correct 28 ms 33256 KB Output is correct
6 Correct 27 ms 33448 KB Output is correct
7 Correct 156 ms 36964 KB Output is correct
8 Correct 26 ms 33352 KB Output is correct
9 Correct 27 ms 33576 KB Output is correct
10 Correct 134 ms 36892 KB Output is correct
11 Correct 92 ms 36776 KB Output is correct
12 Correct 259 ms 37012 KB Output is correct
13 Correct 132 ms 36872 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33240 KB Output is correct
2 Correct 26 ms 33244 KB Output is correct
3 Correct 24 ms 33276 KB Output is correct
4 Correct 28 ms 33252 KB Output is correct
5 Correct 28 ms 33256 KB Output is correct
6 Correct 27 ms 33448 KB Output is correct
7 Correct 156 ms 36964 KB Output is correct
8 Correct 26 ms 33352 KB Output is correct
9 Correct 27 ms 33576 KB Output is correct
10 Correct 134 ms 36892 KB Output is correct
11 Correct 92 ms 36776 KB Output is correct
12 Correct 259 ms 37012 KB Output is correct
13 Correct 132 ms 36872 KB Output is correct
14 Correct 216 ms 39188 KB Output is correct
15 Runtime error 897 ms 132292 KB Execution killed with signal 6
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 33292 KB Output is correct
3 Runtime error 126 ms 72772 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33288 KB Output is correct
2 Correct 23 ms 33272 KB Output is correct
3 Runtime error 63 ms 67308 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33220 KB Output is correct
2 Correct 25 ms 33228 KB Output is correct
3 Runtime error 64 ms 67268 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33236 KB Output is correct
2 Correct 24 ms 33320 KB Output is correct
3 Correct 24 ms 33244 KB Output is correct
4 Runtime error 65 ms 67292 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -