oj.uz

Submission #936422

# Submission time Handle Problem Language Result Execution time Memory
936422 2024-03-01T19:04:03 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
62 / 100
 2641 ms 578288 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;
    	}
    }
}

bool try_compare(int x, int y) {
	int dist = x - y, 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 52 ms 150188 KB Output is correct
2 Correct 22 ms 150120 KB Output is correct
3 Correct 22 ms 150108 KB Output is correct
4 Correct 24 ms 150096 KB Output is correct
5 Correct 20 ms 150108 KB Output is correct
6 Correct 315 ms 152892 KB Output is correct
7 Correct 572 ms 192044 KB Output is correct
8 Correct 1726 ms 267972 KB Output is correct
9 Correct 1671 ms 267328 KB Output is correct
10 Correct 1557 ms 267732 KB Output is correct
11 Correct 1669 ms 274572 KB Output is correct
12 Correct 1615 ms 274496 KB Output is correct
13 Correct 1390 ms 274496 KB Output is correct
14 Correct 1533 ms 274464 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 150092 KB Output is correct
2 Correct 21 ms 150260 KB Output is correct
3 Correct 22 ms 150104 KB Output is correct
4 Correct 22 ms 150108 KB Output is correct
5 Correct 22 ms 150104 KB Output is correct
6 Correct 35 ms 150204 KB Output is correct
7 Correct 125 ms 153300 KB Output is correct
8 Correct 25 ms 150096 KB Output is correct
9 Correct 30 ms 150360 KB Output is correct
10 Correct 106 ms 153552 KB Output is correct
11 Correct 110 ms 153168 KB Output is correct
12 Correct 122 ms 153276 KB Output is correct
13 Correct 112 ms 153680 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 150092 KB Output is correct
2 Correct 21 ms 150260 KB Output is correct
3 Correct 22 ms 150104 KB Output is correct
4 Correct 22 ms 150108 KB Output is correct
5 Correct 22 ms 150104 KB Output is correct
6 Correct 35 ms 150204 KB Output is correct
7 Correct 125 ms 153300 KB Output is correct
8 Correct 25 ms 150096 KB Output is correct
9 Correct 30 ms 150360 KB Output is correct
10 Correct 106 ms 153552 KB Output is correct
11 Correct 110 ms 153168 KB Output is correct
12 Correct 122 ms 153276 KB Output is correct
13 Correct 112 ms 153680 KB Output is correct
14 Correct 258 ms 193240 KB Output is correct
15 Runtime error 2641 ms 578288 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 150108 KB Output is correct
2 Correct 22 ms 150260 KB Output is correct
3 Correct 155 ms 153292 KB Output is correct
4 Correct 1561 ms 274500 KB Output is correct
5 Correct 1674 ms 274504 KB Output is correct
6 Correct 1864 ms 274492 KB Output is correct
7 Correct 2089 ms 275444 KB Output is correct
8 Correct 2247 ms 282944 KB Output is correct
9 Correct 1554 ms 276348 KB Output is correct
10 Correct 1610 ms 276304 KB Output is correct
11 Correct 1366 ms 276288 KB Output is correct
12 Correct 1735 ms 276304 KB Output is correct
13 Correct 1566 ms 281928 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 150108 KB Output is correct
2 Correct 20 ms 150192 KB Output is correct
3 Correct 22 ms 150268 KB Output is correct
4 Correct 21 ms 150108 KB Output is correct
5 Correct 21 ms 150140 KB Output is correct
6 Correct 26 ms 150140 KB Output is correct
7 Correct 73 ms 150868 KB Output is correct
8 Correct 39 ms 150864 KB Output is correct
9 Correct 63 ms 150824 KB Output is correct
10 Correct 40 ms 150876 KB Output is correct
11 Correct 53 ms 150808 KB Output is correct
12 Correct 47 ms 150828 KB Output is correct
13 Correct 32 ms 150948 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 150104 KB Output is correct
2 Correct 21 ms 150108 KB Output is correct
3 Correct 23 ms 150108 KB Output is correct
4 Correct 23 ms 150152 KB Output is correct
5 Correct 27 ms 150080 KB Output is correct
6 Correct 1352 ms 274532 KB Output is correct
7 Correct 1661 ms 274492 KB Output is correct
8 Correct 1867 ms 275516 KB Output is correct
9 Correct 2311 ms 282960 KB Output is correct
10 Correct 1375 ms 276816 KB Output is correct
11 Correct 1646 ms 284688 KB Output is correct
12 Correct 1230 ms 276540 KB Output is correct
13 Correct 1540 ms 276780 KB Output is correct
14 Correct 1642 ms 277168 KB Output is correct
15 Correct 1950 ms 278056 KB Output is correct
16 Correct 1229 ms 276604 KB Output is correct
17 Correct 1388 ms 276760 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 150188 KB Output is correct
2 Correct 22 ms 150120 KB Output is correct
3 Correct 22 ms 150108 KB Output is correct
4 Correct 24 ms 150096 KB Output is correct
5 Correct 20 ms 150108 KB Output is correct
6 Correct 315 ms 152892 KB Output is correct
7 Correct 572 ms 192044 KB Output is correct
8 Correct 1726 ms 267972 KB Output is correct
9 Correct 1671 ms 267328 KB Output is correct
10 Correct 1557 ms 267732 KB Output is correct
11 Correct 1669 ms 274572 KB Output is correct
12 Correct 1615 ms 274496 KB Output is correct
13 Correct 1390 ms 274496 KB Output is correct
14 Correct 1533 ms 274464 KB Output is correct
15 Correct 22 ms 150092 KB Output is correct
16 Correct 21 ms 150260 KB Output is correct
17 Correct 22 ms 150104 KB Output is correct
18 Correct 22 ms 150108 KB Output is correct
19 Correct 22 ms 150104 KB Output is correct
20 Correct 35 ms 150204 KB Output is correct
21 Correct 125 ms 153300 KB Output is correct
22 Correct 25 ms 150096 KB Output is correct
23 Correct 30 ms 150360 KB Output is correct
24 Correct 106 ms 153552 KB Output is correct
25 Correct 110 ms 153168 KB Output is correct
26 Correct 122 ms 153276 KB Output is correct
27 Correct 112 ms 153680 KB Output is correct
28 Correct 258 ms 193240 KB Output is correct
29 Runtime error 2641 ms 578288 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -