oj.uz

Submission #936430

# Submission time Handle Problem Language Result Execution time Memory
936430 2024-03-01T19:18:07 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
75 / 100
 2408 ms 291604 KB 
#include <bits/stdc++.h>
#include "plants.h"

#define x first
#define y second

using ll = long long;
 
using namespace std;
 
const int LG = 19, N = 1 << LG;
int st1[2 * N], st2[2 * N], lz1[2 * N], lz2[2 * N], timer = 1, fndl[2 * N], fndl2[2 * N], used3[N], level[N], kk, nn;
pair<int, int> fnd[2 * N], binupl[LG][N];
pair<int, ll> binupr[LG][N], fnd2[2 * N];
vector<pair<int, int>> mst[2 * N];



void push(int i, int st[], int lz[]) {
	if (lz[i] != -1) {
		st[2 * i + 1] = lz[i];
		st[2 * i + 2] = lz[i];
		lz[2 * i + 1] = lz[i];
		lz[2 * i + 2] = lz[i];
		lz[i] = -1;
	}
}

void set_seg(int l, int r, int x, int st[], int lz[], int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		st[i] = x;
		lz[i] = x;
		return;
	}
	if (l1 > r || r1 < l) {
		return;
	}
	push(i, st, lz);
	set_seg(l, r, x, st, lz, l1, (l1 + r1) / 2, 2 * i + 1);
	set_seg(l, r, x, st, lz, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
	st[i] = min(st[2 * i + 1], st[2 * i + 2]);
}

int get(int ind, int st[], int lz[], int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 == ind && r1 == ind) {
		return st[i];
	}
	if (l1 > ind || r1 < ind) {
		return INT32_MAX;
	}
	push(i, st, lz);
	return min(get(ind, st, lz, l1, (l1 + r1) / 2, 2 * i + 1), get(ind, st, lz, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}

void push(int i) {
	fnd[2 * i + 1].x += fndl[i];
	fnd[2 * i + 2].x += fndl[i];
	fndl[2 * i + 1] += fndl[i];
	fndl[2 * i + 2] += fndl[i];
	fndl[i] = 0;
}

void push1(int i) {
	fnd2[2 * i + 1].x += fndl2[i];
	fnd2[2 * i + 2].x += fndl2[i];
	fndl2[2 * i + 1] += fndl2[i];
	fndl2[2 * i + 2] += fndl2[i];
	fndl2[i] = 0;
}

void add_seg(int l, int r, int x, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		fnd[i].x += x;
		fndl[i] += x;
		return;
	}
	if (l1 > r || r1 < l) {
		return;
	}
	push(i);
	add_seg(l, r, x, l1, (l1 + r1) / 2, 2 * i + 1);
	add_seg(l, r, x, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
	fnd[i] = min(fnd[2 * i + 1], fnd[2 * i + 2]);
}

pair<int, int> get_min(int l, int r, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		return fnd[i];
	}
	if (l1 > r || r1 < l) {
		return {INT32_MAX, -1};
	}
	push(i);
	return min(get_min(l, r, l1, (l1 + r1) / 2, 2 * i + 1), get_min(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}

void add_seg1(int l, int r, int x, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		fnd2[i].x += x;
		fndl2[i] += x;
		return;
	}
	if (l1 > r || r1 < l) {
		return;
	}
	push1(i);
	add_seg1(l, r, x, l1, (l1 + r1) / 2, 2 * i + 1);
	add_seg1(l, r, x, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
	fnd2[i] = min(fnd2[2 * i + 1], fnd2[2 * i + 2]);
}

pair<int, int> get_min1(int l, int r, int l1 = 0, int r1 = N - 1, int i = 0) {
	if (l1 >= l && r1 <= r) {
		return fnd2[i];
	}
	if (l1 > r || r1 < l) {
		return {INT32_MAX, -1};
	}
	push1(i);
	return min(get_min1(l, r, l1, (l1 + r1) / 2, 2 * i + 1), get_min1(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}

pair<int, int> find_max(int i, int v) {
	int l = -1, r = mst[i].size();
	while (r - l > 1) {
		int m = (r + l) / 2;
		if (mst[i][m].x >= v) {
			r = m;
		} else {
			l = m;
		}
	}
	return l == -1 ? make_pair(-1, N) : mst[i][l];
}

pair<int, int> get_max(int l, int r, int v) {
	l += N - 1;
	r += N - 1;
	pair<int, int> res = {-1, -1};
	while (l <= r) {
		if (~l & 1) {
			res = max(res, find_max(l++, v));
		}
		if (r & 1) {
			res = max(res, find_max(r--, v));
		}
		l = (l - 1) / 2;
		r = (r - 1) / 2;
	}
	return res;
}

void mrg(int to, int a, int b) {
	mst[to].resize(mst[a].size() + mst[b].size());
	std::merge(mst[a].begin(), mst[a].end(), mst[b].begin(), mst[b].end(), mst[to].begin());
}

void init(int k, vector<int> r) {
	kk = k;
    int n = r.size();
    nn = n;
    int ok = 0;
    for (int i = 0; i < 2 * N; i++) {
    	st1[i] = -1;
    	st2[i] = -1;
    	lz1[i] = -1;
    	lz2[i] = -1;
    }
    for (int i = 0; i < N; i++) {
    	fnd[i + N - 1].y = i;
    	fnd2[i + N - 1].y = i;
    	level[i] = n;
    }
    for (int i = 0; i < n; i++) {
    	add_seg(i, i, r[i]);
    	add_seg1(i, i, r[i]);
		if (r[i] == 0) {
			used3[i] = 1;
			if (i + k > n) {
				add_seg(i + 1, n - 1, 1);
				add_seg(0, i + k - n - 1, 1);
			} else {
				add_seg(i + 1, i + k - 1, 1);
			}
		}
    }
    while (ok < n) {
    	auto [value, i] = get_min(0, n - 1);
    	// cout << i << '\n';
    	// for (int i = 0; i < n; i++) {
    	// 	cout << get_min(i, i).x << ' ';
    	// }
    	// cout << '\n';
    	if (value) {
    		// cout << value << ' ' << ok << '\n';
    		exit(1);
    	}
    	int tmp1 = get(i, st1, lz1), tmp2 = get(i, st2, lz2);
    	if (tmp1 != -1) {
    		level[i] = min(level[i], level[tmp1] - 1);
    	}
    	if (tmp2 != -1) {
    		level[i] = min(level[i], level[tmp2] - 1);
    	}
    	vector<int> z;
        if (i + k - 1 < n) {
    		set_seg(i + 1, i + k - 1, i, st2, lz2);
    		add_seg(i + 1, i + k - 1, -1);
    	} else {
    		set_seg(i + 1, n - 1, i, st2, lz2);
    		set_seg(0, i + k - 1 - n, i, st2, lz2);
    		add_seg(i + 1, n - 1, -1);
    		add_seg(0, i + k - 1 - n, -1);
    	}
    	if (i >= k - 1) {
    		add_seg(i - k + 1, i - 1, -1);
    		add_seg1(i - k + 1, i - 1, -1);
    		int left = i - k + 1;
    		while (left <= i - 1 && !get_min1(left, i - 1).x) {
    			z.push_back(get_min1(left, i - 1).y);
    			assert(left <= z.back());
    			left = z.back() + 1;
    		}
    		set_seg(i - k + 1, i - 1, i, st1, lz1);
    	} else {
    		add_seg(0, i - 1, -1);
    		add_seg1(0, i - 1, -1);
    		set_seg(0, i - 1, i, st1, lz1);
    		add_seg(n + 1 - k + i, n - 1, -1);
    		add_seg1(n + 1 - k + i, n - 1, -1);
    		set_seg(n + 1 - k + i, n - 1, i, st1, lz1);
    		int left = 0;
    		while (left <= i - 1 && !get_min1(left, i - 1).x) {
    			z.push_back(get_min1(left, i - 1).y);
    			assert(left <= z.back());
    			left = z.back() + 1;
    		}
    		left = n + 1 - k + i;
    		while (left <= n - 1 && !get_min1(left, n - 1).x) {
    			z.push_back(get_min1(left, n - 1).y);
    			assert(left <= z.back());
    			left = z.back() + 1;
    		}
    	}
    	for (int j : z) {
    		if (!used3[j]) {
				if (j + k > n) {
					add_seg(j + 1, n - 1, 1);
					add_seg(0, j + k - n - 1, 1);
				} else {
					add_seg(j + 1, j + k - 1, 1);
				}
				used3[j] = 1;
			}
		}
        add_seg(i, i, INT32_MAX / 2);
        add_seg1(i, i, INT32_MAX / 2);
    	ok++;
    }
    // for (int i = 0; i < n; i++) {
    // 	cout << level[i] << ' ';
    // }
    // cout << '\n';
    // for (int i = 0; i < n; i++) {
    // 	mst[N - 1 + i].emplace_back(level[i], i);
    // }
    // for (int i = N - 2; i >= 0; i--) {
    // 	mrg(i, 2 * i + 1, 2 * i + 2);
    // }
    set<pair<int, int>> st1;
    set<pair<int, int>> st2;
    for (int i = n - k + 1; i < n; i++) {
    	st1.emplace(-level[i], i);
    }
    for (int i = 1; i < k; i++) {
    	st2.emplace(-level[i], i);
    }
    for (int i = 0; i < n; i++) {
    	auto lb1 = st1.lower_bound({-level[i], N});
    	if (lb1 == st1.end()) {
    		binupl[0][i].x = i;
    	} else {
    		binupl[0][i].x = (*lb1).y;
    	}
    	st1.erase({-level[(i - k + 1 + n) % n], (i - k + 1 + n) % n});
    	st1.emplace(-level[i], i);
    	// if (i >= k - 1) {
    	// 	binupl[0][i].x = get_max(i - k + 1, i - 1, level[i]).y;
    	// } else {
    	// 	binupl[0][i].x = max(get_max(0, i - 1, level[i]), get_max(n + i - k + 1, n - 1, level[i])).y;
    	// }
    	// if (binupl[0][i].x == N) {
    	// 	binupl[0][i].x = i;
    	// }
    	binupl[0][i].y = i - binupl[0][i].x;
    	if (binupl[0][i].y < 0) {
    		binupl[0][i].y += n;
    	}
    	auto lb2 = st2.lower_bound({-level[i], N});
    	if (lb2 == st2.end()) {
    		binupr[0][i].x = i;
    	} else {
    		binupr[0][i].x = (*lb2).y;
    	}
    	st2.erase({-level[i + 1], i + 1});
    	st2.emplace(-level[(i + k) % n], (i + k) % n);
    	// if (i + k - 1 < n) {
    	// 	binupr[0][i].x = get_max(i + 1, i + k - 1, level[i]).y;
    	// } else {
    	// 	binupr[0][i].x = max(get_max(i + 1, n - 1, level[i]), get_max(0, i + k - 1 - n, level[i])).y;
    	// }
    	// if (binupr[0][i].x == N) {
    	// 	binupr[0][i].x = i;
    	// }
    	binupr[0][i].y = binupr[0][i].x - i;
    	if (binupr[0][i].y < 0) {
    		binupr[0][i].y += n;
    	}
    }
    for (int l = 1; l < LG; l++) {
    	for (int i = 0; i < n; i++) {
    		binupl[l][i].x = binupl[l - 1][binupl[l - 1][i].x].x;
    		binupr[l][i].x = binupr[l - 1][binupr[l - 1][i].x].x;
    		binupl[l][i].y = binupl[l - 1][binupl[l - 1][i].x].y + binupl[l - 1][i].y;
    		binupr[l][i].y = binupr[l - 1][binupr[l - 1][i].x].y + binupr[l - 1][i].y;
    	}
    }
    for (int i = 0; i < n; i++) {
    	for (int l = 0; l < LG; l++) {
    		// assert(binupl[l][i].y >= 0);
    		// assert(binupr[l][i].y >= 0);
    		assert(binupl[l][i].x >= 0);
    		assert(binupr[l][i].x >= 0);
    		assert(binupl[l][i].x < n);
    		assert(binupr[l][i].x < n);
    	}
    }
}

bool try_compare(int x, int y) {
	ll dist = x - y;
	int nw = x;
	if (dist < 0) {
		dist += nn;
	}
	dist -= kk - 1;
	if (dist <= 0) {
		// cout << "! " << nw << '\n';
		return true;
	} 
	for (int i = LG - 1; i >= 0; i--) {
		if (binupl[i][nw].y < dist) {
			dist -= binupl[i][nw].y;
			nw = binupl[i][nw].x;
		}
	}
	assert(dist > 0);
	dist -= binupl[0][nw].y;
	nw = binupl[0][nw].x;
	if (level[nw] >= level[y] && dist <= 0) {
		// cout << "!! " << nw << '\n';
		return true;
	}
	dist = y - x, nw = x;
	if (dist < 0) {
		dist += nn;
	}
	dist -= kk - 1;
	if (dist <= 0) {
		// cout << "!!! " << nw << '\n';
		return true;
	}
	for (int i = LG - 1; i >= 0; i--) {
		if (binupr[i][nw].y < dist) {
			dist -= binupr[i][nw].y;
			nw = binupr[i][nw].x;
		}
	}
	assert(dist > 0);
	dist -= binupr[0][nw].y;
	nw = binupr[0][nw].x;
	if (level[nw] >= level[y] && dist <= 0) {
		// cout << "!!!! " << nw << '\n';
		return true;
	}
	return false;
}
 
int compare_plants(int x, int y) {
	if (try_compare(x, y) && level[x] > level[y]) {
		return 1;
	}
	if (try_compare(y, x) && level[y] > level[x]) {
		return -1;
	}
	// if (level[x] > level[y]) {
	// 	return 1;
	// }
	// if (level[y] > level[x]) {
	// 	return -1;
	// }
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 150108 KB Output is correct
2 Correct 23 ms 150108 KB Output is correct
3 Correct 21 ms 150108 KB Output is correct
4 Correct 22 ms 150108 KB Output is correct
5 Correct 21 ms 150108 KB Output is correct
6 Correct 394 ms 152892 KB Output is correct
7 Correct 499 ms 180876 KB Output is correct
8 Correct 1863 ms 267068 KB Output is correct
9 Correct 1843 ms 267276 KB Output is correct
10 Correct 1617 ms 268748 KB Output is correct
11 Correct 1652 ms 267204 KB Output is correct
12 Correct 1622 ms 263276 KB Output is correct
13 Correct 1282 ms 187720 KB Output is correct
14 Correct 1639 ms 267276 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 150104 KB Output is correct
2 Correct 21 ms 150108 KB Output is correct
3 Correct 22 ms 150156 KB Output is correct
4 Correct 22 ms 150104 KB Output is correct
5 Correct 22 ms 150096 KB Output is correct
6 Correct 31 ms 150364 KB Output is correct
7 Correct 107 ms 153428 KB Output is correct
8 Correct 23 ms 150616 KB Output is correct
9 Correct 30 ms 150212 KB Output is correct
10 Correct 117 ms 153680 KB Output is correct
11 Correct 121 ms 153296 KB Output is correct
12 Correct 123 ms 69816 KB Output is correct
13 Correct 101 ms 153428 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 150104 KB Output is correct
2 Correct 21 ms 150108 KB Output is correct
3 Correct 22 ms 150156 KB Output is correct
4 Correct 22 ms 150104 KB Output is correct
5 Correct 22 ms 150096 KB Output is correct
6 Correct 31 ms 150364 KB Output is correct
7 Correct 107 ms 153428 KB Output is correct
8 Correct 23 ms 150616 KB Output is correct
9 Correct 30 ms 150212 KB Output is correct
10 Correct 117 ms 153680 KB Output is correct
11 Correct 121 ms 153296 KB Output is correct
12 Correct 123 ms 69816 KB Output is correct
13 Correct 101 ms 153428 KB Output is correct
14 Correct 254 ms 193120 KB Output is correct
15 Correct 2386 ms 238656 KB Output is correct
16 Correct 250 ms 147808 KB Output is correct
17 Correct 2408 ms 182632 KB Output is correct
18 Correct 1365 ms 273104 KB Output is correct
19 Correct 1449 ms 276616 KB Output is correct
20 Correct 2338 ms 291604 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 150276 KB Output is correct
2 Correct 13 ms 68444 KB Output is correct
3 Correct 148 ms 70072 KB Output is correct
4 Correct 1609 ms 270792 KB Output is correct
5 Correct 1848 ms 274624 KB Output is correct
6 Correct 1941 ms 274496 KB Output is correct
7 Correct 2174 ms 275548 KB Output is correct
8 Correct 2203 ms 283308 KB Output is correct
9 Correct 1738 ms 274620 KB Output is correct
10 Correct 1707 ms 274616 KB Output is correct
11 Correct 1392 ms 274772 KB Output is correct
12 Correct 1724 ms 274800 KB Output is correct
13 Correct 1544 ms 280244 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 150104 KB Output is correct
2 Correct 21 ms 150104 KB Output is correct
3 Correct 23 ms 150108 KB Output is correct
4 Correct 22 ms 150100 KB Output is correct
5 Correct 24 ms 150096 KB Output is correct
6 Correct 24 ms 150116 KB Output is correct
7 Correct 49 ms 150716 KB Output is correct
8 Correct 38 ms 150868 KB Output is correct
9 Correct 47 ms 150864 KB Output is correct
10 Correct 36 ms 150868 KB Output is correct
11 Correct 48 ms 150876 KB Output is correct
12 Correct 46 ms 150864 KB Output is correct
13 Correct 32 ms 150864 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 150108 KB Output is correct
2 Correct 22 ms 150096 KB Output is correct
3 Correct 22 ms 150232 KB Output is correct
4 Correct 21 ms 150108 KB Output is correct
5 Correct 30 ms 150180 KB Output is correct
6 Correct 1389 ms 274608 KB Output is correct
7 Correct 1674 ms 275004 KB Output is correct
8 Correct 1815 ms 275520 KB Output is correct
9 Correct 2224 ms 282944 KB Output is correct
10 Correct 1477 ms 274516 KB Output is correct
11 Correct 1614 ms 282192 KB Output is correct
12 Correct 1270 ms 274512 KB Output is correct
13 Correct 1526 ms 274492 KB Output is correct
14 Correct 1658 ms 274528 KB Output is correct
15 Correct 1920 ms 275540 KB Output is correct
16 Correct 1183 ms 274388 KB Output is correct
17 Correct 1412 ms 274512 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 150108 KB Output is correct
2 Correct 23 ms 150108 KB Output is correct
3 Correct 21 ms 150108 KB Output is correct
4 Correct 22 ms 150108 KB Output is correct
5 Correct 21 ms 150108 KB Output is correct
6 Correct 394 ms 152892 KB Output is correct
7 Correct 499 ms 180876 KB Output is correct
8 Correct 1863 ms 267068 KB Output is correct
9 Correct 1843 ms 267276 KB Output is correct
10 Correct 1617 ms 268748 KB Output is correct
11 Correct 1652 ms 267204 KB Output is correct
12 Correct 1622 ms 263276 KB Output is correct
13 Correct 1282 ms 187720 KB Output is correct
14 Correct 1639 ms 267276 KB Output is correct
15 Correct 22 ms 150104 KB Output is correct
16 Correct 21 ms 150108 KB Output is correct
17 Correct 22 ms 150156 KB Output is correct
18 Correct 22 ms 150104 KB Output is correct
19 Correct 22 ms 150096 KB Output is correct
20 Correct 31 ms 150364 KB Output is correct
21 Correct 107 ms 153428 KB Output is correct
22 Correct 23 ms 150616 KB Output is correct
23 Correct 30 ms 150212 KB Output is correct
24 Correct 117 ms 153680 KB Output is correct
25 Correct 121 ms 153296 KB Output is correct
26 Correct 123 ms 69816 KB Output is correct
27 Correct 101 ms 153428 KB Output is correct
28 Correct 254 ms 193120 KB Output is correct
29 Correct 2386 ms 238656 KB Output is correct
30 Correct 250 ms 147808 KB Output is correct
31 Correct 2408 ms 182632 KB Output is correct
32 Correct 1365 ms 273104 KB Output is correct
33 Correct 1449 ms 276616 KB Output is correct
34 Correct 2338 ms 291604 KB Output is correct
35 Correct 21 ms 150276 KB Output is correct
36 Correct 13 ms 68444 KB Output is correct
37 Correct 148 ms 70072 KB Output is correct
38 Correct 1609 ms 270792 KB Output is correct
39 Correct 1848 ms 274624 KB Output is correct
40 Correct 1941 ms 274496 KB Output is correct
41 Correct 2174 ms 275548 KB Output is correct
42 Correct 2203 ms 283308 KB Output is correct
43 Correct 1738 ms 274620 KB Output is correct
44 Correct 1707 ms 274616 KB Output is correct
45 Correct 1392 ms 274772 KB Output is correct
46 Correct 1724 ms 274800 KB Output is correct
47 Correct 1544 ms 280244 KB Output is correct
48 Correct 21 ms 150104 KB Output is correct
49 Correct 21 ms 150104 KB Output is correct
50 Correct 23 ms 150108 KB Output is correct
51 Correct 22 ms 150100 KB Output is correct
52 Correct 24 ms 150096 KB Output is correct
53 Correct 24 ms 150116 KB Output is correct
54 Correct 49 ms 150716 KB Output is correct
55 Correct 38 ms 150868 KB Output is correct
56 Correct 47 ms 150864 KB Output is correct
57 Correct 36 ms 150868 KB Output is correct
58 Correct 48 ms 150876 KB Output is correct
59 Correct 46 ms 150864 KB Output is correct
60 Correct 32 ms 150864 KB Output is correct
61 Correct 210 ms 152912 KB Output is correct
62 Correct 489 ms 192044 KB Output is correct
63 Correct 2206 ms 274612 KB Output is correct
64 Correct 1457 ms 274496 KB Output is correct
65 Correct 1871 ms 274704 KB Output is correct
66 Correct 2036 ms 275520 KB Output is correct
67 Incorrect 2206 ms 282964 KB Output isn't correct
68 Halted 0 ms 0 KB -