oj.uz

Submission #936414

# Submission time Handle Problem Language Result Execution time Memory
936414 2024-03-01T18:56:23 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
44 / 100
 2308 ms 245552 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], 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 (level[nw] > level[y] && 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;
		}
	}
	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 (level[nw] > level[y] && 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;
		}
	}
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 143956 KB Output is correct
2 Correct 22 ms 143964 KB Output is correct
3 Correct 20 ms 143964 KB Output is correct
4 Incorrect 21 ms 143964 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 143964 KB Output is correct
2 Correct 21 ms 143952 KB Output is correct
3 Correct 22 ms 143964 KB Output is correct
4 Correct 20 ms 143964 KB Output is correct
5 Correct 22 ms 144276 KB Output is correct
6 Correct 30 ms 144044 KB Output is correct
7 Correct 99 ms 147268 KB Output is correct
8 Correct 22 ms 143992 KB Output is correct
9 Correct 28 ms 144216 KB Output is correct
10 Correct 107 ms 147280 KB Output is correct
11 Correct 86 ms 147020 KB Output is correct
12 Correct 89 ms 147140 KB Output is correct
13 Correct 100 ms 147284 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 143964 KB Output is correct
2 Correct 21 ms 143952 KB Output is correct
3 Correct 22 ms 143964 KB Output is correct
4 Correct 20 ms 143964 KB Output is correct
5 Correct 22 ms 144276 KB Output is correct
6 Correct 30 ms 144044 KB Output is correct
7 Correct 99 ms 147268 KB Output is correct
8 Correct 22 ms 143992 KB Output is correct
9 Correct 28 ms 144216 KB Output is correct
10 Correct 107 ms 147280 KB Output is correct
11 Correct 86 ms 147020 KB Output is correct
12 Correct 89 ms 147140 KB Output is correct
13 Correct 100 ms 147284 KB Output is correct
14 Correct 225 ms 148032 KB Output is correct
15 Correct 2238 ms 238252 KB Output is correct
16 Correct 209 ms 147972 KB Output is correct
17 Correct 2308 ms 238364 KB Output is correct
18 Correct 1192 ms 236460 KB Output is correct
19 Correct 1235 ms 236868 KB Output is correct
20 Correct 2101 ms 245552 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 143964 KB Output is correct
2 Correct 21 ms 143960 KB Output is correct
3 Correct 71 ms 146888 KB Output is correct
4 Correct 874 ms 226640 KB Output is correct
5 Correct 1103 ms 227272 KB Output is correct
6 Correct 1412 ms 227376 KB Output is correct
7 Correct 1678 ms 228320 KB Output is correct
8 Correct 2087 ms 235824 KB Output is correct
9 Correct 974 ms 230392 KB Output is correct
10 Correct 1002 ms 230664 KB Output is correct
11 Correct 651 ms 230292 KB Output is correct
12 Correct 863 ms 229712 KB Output is correct
13 Correct 1102 ms 236372 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 144076 KB Output is correct
2 Correct 21 ms 143964 KB Output is correct
3 Incorrect 20 ms 143964 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 144008 KB Output is correct
2 Correct 21 ms 143992 KB Output is correct
3 Incorrect 21 ms 143964 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 143956 KB Output is correct
2 Correct 22 ms 143964 KB Output is correct
3 Correct 20 ms 143964 KB Output is correct
4 Incorrect 21 ms 143964 KB Output isn't correct
5 Halted 0 ms 0 KB -