oj.uz

Submission #425694

# Submission time Handle Problem Language Result Execution time Memory
425694 2021-06-13T10:15:01 Z Mlxa Comparing Plants (IOI20_plants) C++14
25 / 100
 231 ms 25908 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "plants.h"
#define cerr if (0) cout

namespace my {

const int L = 17;
const int N = 1 << L;
int n, k, kth[N], can[N];

struct tree_t {
	pair<int, int> mi[2 * N];
	int pu[2 * N];
	int ls(int v) {
		return 2 * v + 1;
	}
	int rs(int v) {
		return 2 * v + 2;
	}
	void build(int v, int l, int r) {
		if (r - l == 1) {
			mi[v] = mp(kth[l], l);
		} else {
			int m = (l + r) / 2;
			build(ls(v), l, m);
			build(rs(v), m, r);
			mi[v] = min(mi[ls(v)], mi[rs(v)]);
		}
	}
	void build() {
		build(0, 0, N);
	}
	void push(int v) {
		mi[ls(v)].x += pu[v];
		mi[rs(v)].x += pu[v];
		pu[ls(v)] += pu[v];
		pu[rs(v)] += pu[v];
		pu[v] = 0;
	}
	void upd(int v, int vl, int vr, int ql, int qr, int d) {
		if (ql <= vl && vr <= qr) {
			mi[v].x += d;
			pu[v] += d;
			return;
		}
		if (qr <= vl || vr <= ql) {
			return;
		}
		push(v);
		int vm = (vl + vr) / 2;
		upd(ls(v), vl, vm, ql, qr, d);
		upd(rs(v), vm, vr, ql, qr, d);
		mi[v] = min(mi[ls(v)], mi[rs(v)]);
	}
	void range_add(int l, int r, int value) {
		upd(0, 0, N, l, r, value);
	}
	void cycle_add(int from, int value) {
		from %= n; from += n; from %= n;
		if (from + k <= n) {
			range_add(from, from + k, value);
		} else {
			range_add(from, n, value), range_add(0, from + k - n, value);
		}
	}
	pair<int, int> query(int v, int vl, int vr, int ql, int qr) {
		if (ql <= vl && vr <= qr) {
			return mi[v];
		}
		if (qr <= vl || vr <= ql) {
			return mp(N, -1);
		}
		int vm = (vl + vr) / 2;
		push(v);
		return min(query(ls(v), vl, vm, ql, qr), query(rs(v), vm, vr, ql, qr));
	}
	pair<int, int> range_min(int l, int r) {
		return query(0, 0, N, l, r);
	}
	pair<int, int> cycle_min(int from) {
		from %= n; from += n; from %= n;
		if (from + k <= n) {
			return range_min(from, from + k);
		} else {
			return min(range_min(from, n), range_min(0, from + k - n));
		}
	}
} tree;

vector<int> topsort;

void extract(int v) {
	tree.range_add(v, v + 1, N);
	while (1) {
		auto e = tree.cycle_min(v - k + 1);
		if (e.x) break;
		extract(e.y);
	}
	tree.cycle_add(v - k + 1, -1);
	topsort.push_back(v);
}

const int BAD = -1;
int lef[L][N], rig[L][N];
}

bool btw(int l, int r, int w) {
	if (l <= r) {
		return l <= w && w <= r;
	} else {
		return l <= w || w <= r;
	}
}

void init(int _k, vector<int> _r) {
	using namespace my;
	n = (int)_r.size();
	k = _k;
	copy(all(_r), kth);
	tree.build();
	while (1) {
		auto e = tree.range_min(0, n);
		if (e.x) break;
		extract(e.y);
	}
	assert((int)topsort.size() == n);
	reverse(all(topsort));
	for (int i = 0; i < n; ++i) {
		can[topsort[i]] = i;
	}
	set<pair<int, int>> iset;
	for (int i = 0; i < k - 1; ++i) {
		iset.emplace(can[i], i);
	}
	fill_n(lef[0], L * N, BAD), fill_n(rig[0], L * N, BAD);
	for (int i = k - 1;;) {
		auto it = iset.lower_bound(mp(can[i], i));
		if (it != iset.begin()) {
			--it;
			lef[0][i] = it->y;
		}
		iset.erase({can[(i + n - k + 1) % n], (i + n - k + 1) % n});
		iset.emplace(can[i], i);
		(i += 1) %= n;
		if (i == k - 1) break;
	}
	iset.clear();
	for (int i = 0; i < k - 1; ++i) {
		iset.emplace(can[i], i);
	}
	for (int i = n - 1; i >= 0; --i) {
		auto it = iset.lower_bound(mp(can[i], i));
		if (it != iset.begin()) {
			--it;
			rig[0][i] = it->y;
		}
		iset.erase({can[(i + k - 1) % n], (i + k - 1) % n});
		iset.emplace(can[i], i);
	}
	for (int i = 0; i < n; ++i) {
		cerr << i << " " << lef[0][i] << " " << rig[0][i] << endl;
	}
	for (int i = 0; i < n; ++i) {
		cerr << can[i] << " ";
	}
	cerr << endl;
	for (int it = 1; it < L; ++it) {
		for (int i = 0; i < n; ++i) {
			if (lef[it - 1][i] != BAD) {
				int j = lef[it - 1][i];
				if (j == BAD || btw(lef[it - 1][j], j, i)) {
					continue;
				}
				lef[it][i] = lef[it - 1][j];
			}
		}
	}
	for (int it = 1; it < L; ++it) {
		for (int i = 0; i < n; ++i) {
			if (rig[it - 1][i] != BAD) {
				int j = rig[it - 1][i];
				if (j == BAD || btw(j, rig[it - 1][j], i)) {
					continue;
				}
				rig[it][i] = rig[it - 1][j];
			}
		}
	}
}

bool taller(int x, int y) {
	using namespace my;
	cerr << "taller " << x << " " << y << endl;
	int z = x;
	for (int it = L - 1; it >= 0; --it) {
		int v = lef[it][z];
		cerr << it << " " << z << " " << v << endl;
		if (v == BAD || btw(v, z, y)) {
			continue;
		}
		z = v;
	}
	cerr << "z = " << z << " " << y << endl;
	assert(lef[0][z] == BAD || btw(lef[0][z], z, y));
	if (lef[0][z] != BAD && btw(lef[0][z], z, y) && can[z] >= can[y]) {
		return true;
	}
	z = x;
	for (int it = L - 1; it >= 0; --it) {
		int v = rig[it][z];
		if (v == BAD || btw(z, v, y)) {
			continue;
		}
		z = v;
	}
	assert(rig[0][z] == BAD || btw(z, rig[0][z], y));
	cerr << "z = " << z << endl;
	if (rig[0][z] != BAD && btw(z, rig[0][z], y) && can[z] >= can[y]) {
		return true;
	}
	return false;
}

int compare_plants(int x, int y) {
	if (taller(x, y)) {
		return 1;
	} else if (taller(y, x)) {
		return -1;
	} else {
		return 0;
	}
}

#ifdef LC
#include "grader.cpp"
#endif

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19832 KB Output is correct
2 Correct 13 ms 19780 KB Output is correct
3 Correct 14 ms 19768 KB Output is correct
4 Correct 13 ms 19760 KB Output is correct
5 Correct 14 ms 19736 KB Output is correct
6 Correct 104 ms 23600 KB Output is correct
7 Correct 211 ms 25332 KB Output is correct
8 Runtime error 85 ms 16580 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19788 KB Output is correct
2 Correct 12 ms 19788 KB Output is correct
3 Correct 14 ms 19788 KB Output is correct
4 Correct 15 ms 19772 KB Output is correct
5 Correct 14 ms 19788 KB Output is correct
6 Correct 20 ms 19976 KB Output is correct
7 Correct 143 ms 24776 KB Output is correct
8 Correct 15 ms 19936 KB Output is correct
9 Correct 19 ms 19896 KB Output is correct
10 Correct 160 ms 24820 KB Output is correct
11 Correct 145 ms 24688 KB Output is correct
12 Correct 203 ms 24836 KB Output is correct
13 Correct 152 ms 24932 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19788 KB Output is correct
2 Correct 12 ms 19788 KB Output is correct
3 Correct 14 ms 19788 KB Output is correct
4 Correct 15 ms 19772 KB Output is correct
5 Correct 14 ms 19788 KB Output is correct
6 Correct 20 ms 19976 KB Output is correct
7 Correct 143 ms 24776 KB Output is correct
8 Correct 15 ms 19936 KB Output is correct
9 Correct 19 ms 19896 KB Output is correct
10 Correct 160 ms 24820 KB Output is correct
11 Correct 145 ms 24688 KB Output is correct
12 Correct 203 ms 24836 KB Output is correct
13 Correct 152 ms 24932 KB Output is correct
14 Correct 231 ms 25908 KB Output is correct
15 Runtime error 83 ms 17248 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19788 KB Output is correct
2 Correct 14 ms 19788 KB Output is correct
3 Correct 144 ms 24384 KB Output is correct
4 Runtime error 79 ms 16476 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19788 KB Output is correct
2 Correct 14 ms 19788 KB Output is correct
3 Correct 14 ms 19788 KB Output is correct
4 Correct 12 ms 19788 KB Output is correct
5 Correct 12 ms 19772 KB Output is correct
6 Correct 15 ms 19904 KB Output is correct
7 Correct 40 ms 20676 KB Output is correct
8 Correct 36 ms 20684 KB Output is correct
9 Correct 36 ms 20676 KB Output is correct
10 Correct 31 ms 20752 KB Output is correct
11 Correct 37 ms 20804 KB Output is correct
12 Correct 36 ms 20692 KB Output is correct
13 Correct 34 ms 20748 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19788 KB Output is correct
2 Correct 12 ms 19788 KB Output is correct
3 Correct 12 ms 19768 KB Output is correct
4 Correct 12 ms 19832 KB Output is correct
5 Correct 18 ms 19792 KB Output is correct
6 Runtime error 73 ms 15712 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19832 KB Output is correct
2 Correct 13 ms 19780 KB Output is correct
3 Correct 14 ms 19768 KB Output is correct
4 Correct 13 ms 19760 KB Output is correct
5 Correct 14 ms 19736 KB Output is correct
6 Correct 104 ms 23600 KB Output is correct
7 Correct 211 ms 25332 KB Output is correct
8 Runtime error 85 ms 16580 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -