oj.uz

Submission #817743

# Submission time Handle Problem Language Result Execution time Memory
817743 2023-08-09T15:29:56 Z hugo_pm Comparing Plants (IOI20_plants) C++17
70 / 100
 610 ms 64712 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define sz(v) ((int)((v).size()))

template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }

using pii = pair<int, int>;
using vi = vector<int>;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int INF = 1e9;
struct ArgMax {
	inline pii op(pii a, pii b) { return max(a, b); }
	const pii e {-INF, -1};
	int N;
	vector<pii> tree, lazy;
	ArgMax(int __n) {
		N = 1;
		while (N < __n) N *= 2;
		tree.assign(2*N, e);
		lazy.assign(2*N, e);
	}
	void update(int i, int x) {
		i += N;
		tree[i] = {x, i-N};
		while (i > 1) {
			i /= 2;
			tree[i] = op(tree[2*i], tree[2*i+1]);
		}
	}
	pii _query(int L, int R) {
		L += N, R += N+1;
		pii res = e;
		while (L < R) {
			if (L & 1) res = op(res, tree[L++]);
			if (R & 1) res = op(res, tree[--R]);
			L /= 2, R /= 2;
		}
		return res;
	}
	int circMax(int L, int R) {
		return (L > R ? max(_query(L, N-1), _query(0, R)) : _query(L, R)).second;
	}
};

struct MinAdd {
	inline int op(int a, int b) { return min(a, b); }
	const int e = INF;
	int N;
	vector<int> tree, lazy;
	void init(vector<int> v) {
		N = 1;
		while (N < (int)v.size()) N *= 2;
		tree.assign(2*N, e);
		lazy.assign(2*N, 0);
		for (int i = 0; i < (int)v.size(); ++i) {
			tree[N+i] = v[i];
		}
		for (int i = N-1; i >= 1; --i) {
			tree[i] = op(tree[2*i], tree[2*i+1]);
		}
	}
	void push(int node) {
		tree[node] += lazy[node];
		if (node < N) {
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node] = 0;
	}
	void _add(int lq, int rq, int delta) {
		auto F = [&] (auto f, int node, int lno, int rno) -> void {
			push(node);
			if (lq <= lno && rno <= rq) {
				lazy[node] += delta;
				push(node);
			} else if (lno <= rq && lq <= rno) {
				int mid = (lno+rno)/2;
				f(f, 2*node, lno, mid);
				f(f, 2*node+1, mid+1, rno);
				tree[node] = op(tree[2*node], tree[2*node+1]);
			}
		};
		F(F, 1, 0, N-1);
	}
	optional<int> _popZero(int lq, int rq) {
		optional<int> ret = nullopt;
		auto F = [&] (auto f, int node, int lno, int rno) {
			push(node);
			if (ret || tree[node] > 0 || rno < lq || rq < lno) {
				return;
			} else if (node >= N) {
				tree[node] = e;
				ret = node - N;
			} else {
				int mid = (lno+rno)/2;
				f(f, 2*node, lno, mid);
				f(f, 2*node+1, mid+1, rno);
				tree[node] = op(tree[2*node], tree[2*node+1]);
			}
		};
		F(F, 1, 0, N-1);
		return ret;
	}
	optional<int> circleGet(int L, int R) {
		if (L > R) {
			auto a = _popZero(L, N-1);
			return (a ? a : _popZero(0, R));
		}
		return _popZero(L, R);
	}
	void circleDecr(int L, int R) {
		if (L > R) {
			_add(L, N-1, -1);
			_add(0, R, -1);
		} else {
			_add(L, R, -1);
		}
	}
};
MinAdd util;

int N, K;
int add(int x, int y) {
	x += y;
	if (x >= N) x -= N;
	return x;
}
int sub(int x, int y) {
	x -= y;
	if (x < 0) x += N;
	return x;
}

vector<int> relative, height;
int insertHeight;

bool pop(int L, int R) {
	optional<int> ret = util.circleGet(L, R);
	if (!ret) return false;
	for (; ret; ret = util.circleGet(L, R)) {
		int cur = *ret;
		pop(sub(cur,K-1), sub(cur, 1));
		height[cur] = insertHeight--;
		util.circleDecr(sub(cur,K-1), sub(cur,1));
	}
	return true;
}

vector<int> lft, rgt;
vector<vi> adjDom, adjAnti;
void addEdge(int u, int v) {
	if (u != -1 && v != -1) {
		adjDom[u].push_back(v);
		adjAnti[v].push_back(u);
	}
}
vector<vector<bool>> matDom, matAnti;
void init(int _k, std::vector<int> _r) {
	K = _k;
	relative = _r;
	N = _r.size();
	//--
	util.init(relative);
	height.assign(N, -1);
	insertHeight = N-1;
	while(pop(0, N-1));
	dbg(height);
	//-
	adjDom.resize(N), adjAnti.resize(N), matDom.resize(N), matAnti.resize(N);
	ArgMax st(N);
	vector<int> order(N);
	iota(all(order), 0);
	sort(all(order), [&] (int i, int j) { return height[i] < height[j]; });
	for (int i : order) {
		addEdge(i, st.circMax(sub(i,K-1), sub(i,1)));
		addEdge(i, st.circMax(add(i,1), add(i,K-1)));
		st.update(i, height[i]);
	}
}

void bfs(int depart, const vector<vi> &adj, vector<bool> &acces) {
	acces.assign(N, false);
	vector<int> stk;
	acces[depart] = true, stk.push_back(depart);
	dbg(depart, adj);
	while (!stk.empty()) {
		int node = stk.back();
		stk.pop_back();
		for (int voisin : adj[node]) {
			if (!acces[voisin]) {
				dbg(node, voisin);
				acces[voisin] = true;
				stk.push_back(voisin);
			}
		}
	}
}
int compare_plants(int x, int y) {
	if (2*K > N || (N > 300 && x != 0))
		return (height[x] > height[y])- (height[y] > height[x]);
	if (matDom[x].empty()) {
		bfs(x, adjDom, matDom[x]);
		bfs(x, adjAnti, matAnti[x]);
	}
	return matDom[x][y] - matAnti[x][y];
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 39 ms 4056 KB Output is correct
7 Incorrect 68 ms 9292 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 49 ms 5436 KB Output is correct
8 Correct 3 ms 436 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 50 ms 5448 KB Output is correct
11 Correct 48 ms 5316 KB Output is correct
12 Correct 46 ms 5560 KB Output is correct
13 Correct 48 ms 5420 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 49 ms 5436 KB Output is correct
8 Correct 3 ms 436 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 50 ms 5448 KB Output is correct
11 Correct 48 ms 5316 KB Output is correct
12 Correct 46 ms 5560 KB Output is correct
13 Correct 48 ms 5420 KB Output is correct
14 Correct 85 ms 9444 KB Output is correct
15 Correct 542 ms 57504 KB Output is correct
16 Correct 78 ms 10528 KB Output is correct
17 Correct 513 ms 59352 KB Output is correct
18 Correct 418 ms 59232 KB Output is correct
19 Correct 342 ms 59200 KB Output is correct
20 Correct 501 ms 59204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 44 ms 4680 KB Output is correct
4 Correct 314 ms 62656 KB Output is correct
5 Correct 361 ms 59764 KB Output is correct
6 Correct 459 ms 59340 KB Output is correct
7 Correct 516 ms 59332 KB Output is correct
8 Correct 523 ms 59448 KB Output is correct
9 Correct 374 ms 59640 KB Output is correct
10 Correct 344 ms 59200 KB Output is correct
11 Correct 285 ms 59308 KB Output is correct
12 Correct 263 ms 59176 KB Output is correct
13 Correct 392 ms 59236 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 10 ms 1280 KB Output is correct
8 Correct 11 ms 1248 KB Output is correct
9 Correct 10 ms 1260 KB Output is correct
10 Correct 10 ms 1364 KB Output is correct
11 Correct 10 ms 1252 KB Output is correct
12 Correct 10 ms 1236 KB Output is correct
13 Correct 9 ms 1332 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 358 ms 58596 KB Output is correct
7 Correct 487 ms 58932 KB Output is correct
8 Correct 550 ms 59124 KB Output is correct
9 Correct 587 ms 59240 KB Output is correct
10 Correct 378 ms 58932 KB Output is correct
11 Correct 527 ms 59268 KB Output is correct
12 Correct 329 ms 64712 KB Output is correct
13 Correct 389 ms 59216 KB Output is correct
14 Correct 476 ms 58924 KB Output is correct
15 Correct 610 ms 59084 KB Output is correct
16 Correct 357 ms 58460 KB Output is correct
17 Correct 394 ms 58824 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 39 ms 4056 KB Output is correct
7 Incorrect 68 ms 9292 KB Output isn't correct
8 Halted 0 ms 0 KB -