oj.uz

Submission #826328

# Submission time Handle Problem Language Result Execution time Memory
826328 2023-08-15T12:56:14 Z NothingXD Comparing Plants (IOI20_plants) C++17
100 / 100
 1615 ms 85272 KB 
#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;
const int lg = 20;
const int inf = 1e6;

int n, k, a[maxn], idx[maxn], ver[maxn], seg[maxn << 2][3], lazy[maxn << 2][3];
ll par[2][maxn][lg];

void shift(int v, int x, int l, int r);

void add(int v, int x, int l, int r, int ql, int qr, int val){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		seg[v][x] += val;
		lazy[v][x] += val;
		return;
	}
	shift(v, x, l, r);
	int mid = (l + r) >> 1;
	add(v << 1, x, l, mid, ql, qr, val);
	add(v << 1 | 1, x, mid, r, ql, qr, val);
	seg[v][x] = min(seg[v<<1][x], seg[v<<1|1][x]);
}

int find0(int v, int x, int l, int r){
	if (seg[v][x] != 0) return -1;
	if (l + 1 == r) return l;
	shift(v, x, l, r);
	int mid = (l + r) >> 1;
	int res = find0(v << 1, x, l, mid);
	if (res == -1) return find0(v << 1 | 1, x, mid, r);
	return res;
}

void shift(int v, int x, int l, int r){
	if (lazy[v][x] == 0) return;
	int mid = (l + r) >> 1;
	add(v << 1, x, l, mid, l, mid, lazy[v][x]);
	add(v << 1 | 1, x, mid, r, mid, r, lazy[v][x]);
	lazy[v][x] = 0;
}

int get(int v, int x, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return inf;
	if (ql <= l && r <= qr) return seg[v][x];
	shift(v, x, l, r);
	int mid = (l + r) >> 1;
	return min(get(v << 1, x, l, mid, ql, qr)
			, get(v << 1 | 1, x, mid, r, ql, qr));
}

void init(int _k, std::vector<int> r) {
	n = r.size();
	k = _k;
	for (int i = 0; i < n; i++){
		a[i] = r[i];
		add(1, 0, 0, n, i, i+1, a[i]);
		add(1, 1, 0, n, i, i+1, a[i]);
		add(1, 2, 0, n, i, i+1, inf);
	}
	vector<int> topol;
	for (int rng = 0; rng < n; rng++){
		int tmp;
		while((tmp = find0(1, 1, 0, n)) != -1){
			add(1, 0, 0, n, tmp+1, tmp+k, 1);
			if (tmp+k > n){
				add(1, 0, 0, n, 0, tmp+k-n, 1);
			}
			add(1, 1, 0, n, tmp, tmp+1, inf);
		}
		tmp = find0(1, 0, 0, n);
		add(1, 0, 0, n, tmp+1, tmp+k, -1);
		if (tmp+k > n){
			add(1, 0, 0, n, 0, tmp+k-n, -1);
		}
		add(1, 0, 0, n, tmp-k+1, tmp, -1);
		add(1, 1, 0, n, tmp-k+1, tmp, -1);
		if (tmp-k+1 < 0){
			add(1, 0, 0, n, tmp-k+1+n, n, -1);
			add(1, 1, 0, n, tmp-k+1+n, n, -1);
		}
		int mn1 = get(1, 2, 0, n, tmp+1, tmp+k);
		int mn2 = get(1, 2, 0, n, tmp-k+1, tmp);
		if (tmp+k > n){
			mn1 = min(mn1, get(1, 2, 0, n, 0, tmp+k-n));
		}
		if (tmp-k+1 < 0){
			mn2 = min(mn2, get(1, 2, 0, n, tmp-k+1+n, n));
		}
		if (mn1 != inf){
//			debug(tmp, ver[mn1]);
			par[0][tmp][0] = (ver[mn1]-tmp+n) % n;
			for (int i = 1; i < lg; i++){
				par[0][tmp][i] = par[0][tmp][i-1] + par[0][(tmp+par[0][tmp][i-1])%n][i-1];
//				debug(i, par[0][tmp][i]);
			}
		}
		if (mn2 != inf){
//			debug(tmp, ver[mn2]);
			par[1][tmp][0] = (tmp-ver[mn2]+n) % n;
			for (int i = 1; i < lg; i++){
				par[1][tmp][i] = par[1][tmp][i-1] + par[1][((tmp-par[1][tmp][i-1])%n+n)%n][i-1];
//				debug(i, par[1][tmp][i]);
			}
		}
		ver[n-rng] = tmp;
		idx[tmp] = n-rng;
		assert(tmp != -1);
		add(1, 0, 0, n, tmp, tmp+1, inf);
		add(1, 2, 0, n, tmp, tmp+1, (n-rng)-inf);
	}
}

bool ok(int x, int y){
//	debug(x, y);
	int v = x;
	int dis = (y - x + n) % n;
//	debug(v, dis);
	for (int i = lg-1; ~i; i--){
		if (par[0][v][i] <= dis){
			dis -= par[0][v][i];
			v = (v+par[0][v][i]) % n;
		}
	}
//	debug(v);
	if (v == y || (idx[y] > idx[v] && dis < k)) return true;
	v = x;
	dis = (x - y + n) % n;
//	debug(v, dis);
	for (int i = lg-1; ~i; i--){
		if (par[1][v][i] <= dis){
			dis -= par[1][v][i];
			v = (v-par[1][v][i]+n) % n;
		}
	}
	//debug(v);
	if (v == y || (idx[y] > idx[v] && dis < k)) return true;
	return false;
}

int compare_plants(int x, int y) {
	return (ok(x, y)? -1: (ok(y, x)? 1: 0));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 112 ms 4060 KB Output is correct
7 Correct 166 ms 10700 KB Output is correct
8 Correct 797 ms 80748 KB Output is correct
9 Correct 764 ms 58260 KB Output is correct
10 Correct 779 ms 52488 KB Output is correct
11 Correct 947 ms 51616 KB Output is correct
12 Correct 805 ms 51524 KB Output is correct
13 Correct 904 ms 51508 KB Output is correct
14 Correct 783 ms 51556 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 75 ms 7024 KB Output is correct
8 Correct 3 ms 392 KB Output is correct
9 Correct 7 ms 832 KB Output is correct
10 Correct 78 ms 7028 KB Output is correct
11 Correct 140 ms 6628 KB Output is correct
12 Correct 79 ms 6752 KB Output is correct
13 Correct 71 ms 7020 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 75 ms 7024 KB Output is correct
8 Correct 3 ms 392 KB Output is correct
9 Correct 7 ms 832 KB Output is correct
10 Correct 78 ms 7028 KB Output is correct
11 Correct 140 ms 6628 KB Output is correct
12 Correct 79 ms 6752 KB Output is correct
13 Correct 71 ms 7020 KB Output is correct
14 Correct 162 ms 13516 KB Output is correct
15 Correct 1537 ms 85172 KB Output is correct
16 Correct 171 ms 13612 KB Output is correct
17 Correct 1500 ms 85212 KB Output is correct
18 Correct 1171 ms 69136 KB Output is correct
19 Correct 1073 ms 69636 KB Output is correct
20 Correct 1431 ms 85272 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 107 ms 3844 KB Output is correct
4 Correct 1056 ms 84036 KB Output is correct
5 Correct 1066 ms 84572 KB Output is correct
6 Correct 1348 ms 84700 KB Output is correct
7 Correct 1381 ms 85000 KB Output is correct
8 Correct 1615 ms 85088 KB Output is correct
9 Correct 1152 ms 84328 KB Output is correct
10 Correct 1110 ms 84360 KB Output is correct
11 Correct 969 ms 51492 KB Output is correct
12 Correct 868 ms 53228 KB Output is correct
13 Correct 1210 ms 62704 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 29 ms 1320 KB Output is correct
8 Correct 18 ms 1328 KB Output is correct
9 Correct 24 ms 1328 KB Output is correct
10 Correct 18 ms 1328 KB Output is correct
11 Correct 28 ms 1340 KB Output is correct
12 Correct 22 ms 1364 KB Output is correct
13 Correct 13 ms 1332 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 1052 ms 83648 KB Output is correct
7 Correct 1191 ms 83880 KB Output is correct
8 Correct 1414 ms 84044 KB Output is correct
9 Correct 1431 ms 84208 KB Output is correct
10 Correct 966 ms 83528 KB Output is correct
11 Correct 1236 ms 84248 KB Output is correct
12 Correct 954 ms 83180 KB Output is correct
13 Correct 1038 ms 83708 KB Output is correct
14 Correct 1211 ms 83928 KB Output is correct
15 Correct 1302 ms 84128 KB Output is correct
16 Correct 877 ms 83404 KB Output is correct
17 Correct 985 ms 83660 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 112 ms 4060 KB Output is correct
7 Correct 166 ms 10700 KB Output is correct
8 Correct 797 ms 80748 KB Output is correct
9 Correct 764 ms 58260 KB Output is correct
10 Correct 779 ms 52488 KB Output is correct
11 Correct 947 ms 51616 KB Output is correct
12 Correct 805 ms 51524 KB Output is correct
13 Correct 904 ms 51508 KB Output is correct
14 Correct 783 ms 51556 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 6 ms 724 KB Output is correct
21 Correct 75 ms 7024 KB Output is correct
22 Correct 3 ms 392 KB Output is correct
23 Correct 7 ms 832 KB Output is correct
24 Correct 78 ms 7028 KB Output is correct
25 Correct 140 ms 6628 KB Output is correct
26 Correct 79 ms 6752 KB Output is correct
27 Correct 71 ms 7020 KB Output is correct
28 Correct 162 ms 13516 KB Output is correct
29 Correct 1537 ms 85172 KB Output is correct
30 Correct 171 ms 13612 KB Output is correct
31 Correct 1500 ms 85212 KB Output is correct
32 Correct 1171 ms 69136 KB Output is correct
33 Correct 1073 ms 69636 KB Output is correct
34 Correct 1431 ms 85272 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 107 ms 3844 KB Output is correct
38 Correct 1056 ms 84036 KB Output is correct
39 Correct 1066 ms 84572 KB Output is correct
40 Correct 1348 ms 84700 KB Output is correct
41 Correct 1381 ms 85000 KB Output is correct
42 Correct 1615 ms 85088 KB Output is correct
43 Correct 1152 ms 84328 KB Output is correct
44 Correct 1110 ms 84360 KB Output is correct
45 Correct 969 ms 51492 KB Output is correct
46 Correct 868 ms 53228 KB Output is correct
47 Correct 1210 ms 62704 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 0 ms 340 KB Output is correct
50 Correct 0 ms 340 KB Output is correct
51 Correct 0 ms 340 KB Output is correct
52 Correct 1 ms 308 KB Output is correct
53 Correct 5 ms 468 KB Output is correct
54 Correct 29 ms 1320 KB Output is correct
55 Correct 18 ms 1328 KB Output is correct
56 Correct 24 ms 1328 KB Output is correct
57 Correct 18 ms 1328 KB Output is correct
58 Correct 28 ms 1340 KB Output is correct
59 Correct 22 ms 1364 KB Output is correct
60 Correct 13 ms 1332 KB Output is correct
61 Correct 135 ms 5492 KB Output is correct
62 Correct 208 ms 13424 KB Output is correct
63 Correct 960 ms 83936 KB Output is correct
64 Correct 1041 ms 84520 KB Output is correct
65 Correct 1249 ms 84772 KB Output is correct
66 Correct 1332 ms 84988 KB Output is correct
67 Correct 1486 ms 85264 KB Output is correct
68 Correct 1053 ms 84456 KB Output is correct
69 Correct 1301 ms 85196 KB Output is correct
70 Correct 1102 ms 83956 KB Output is correct
71 Correct 1131 ms 84592 KB Output is correct
72 Correct 1324 ms 84832 KB Output is correct
73 Correct 1437 ms 84944 KB Output is correct
74 Correct 951 ms 84212 KB Output is correct
75 Correct 992 ms 84656 KB Output is correct