oj.uz

Submission #936425

# Submission time Handle Problem Language Result Execution time Memory
936425 2024-03-01T19:08:59 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
75 / 100
 2436 ms 293204 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) {
	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 44 ms 150228 KB Output is correct
2 Correct 21 ms 150264 KB Output is correct
3 Correct 21 ms 150108 KB Output is correct
4 Correct 21 ms 150108 KB Output is correct
5 Correct 21 ms 150108 KB Output is correct
6 Correct 449 ms 152888 KB Output is correct
7 Correct 443 ms 192340 KB Output is correct
8 Correct 1646 ms 274512 KB Output is correct
9 Correct 1508 ms 274428 KB Output is correct
10 Correct 1510 ms 274640 KB Output is correct
11 Correct 1561 ms 274512 KB Output is correct
12 Correct 1554 ms 274384 KB Output is correct
13 Correct 1341 ms 274612 KB Output is correct
14 Correct 1509 ms 274764 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 150104 KB Output is correct
3 Correct 22 ms 150108 KB Output is correct
4 Correct 21 ms 150100 KB Output is correct
5 Correct 23 ms 150108 KB Output is correct
6 Correct 29 ms 150364 KB Output is correct
7 Correct 122 ms 153424 KB Output is correct
8 Correct 23 ms 150360 KB Output is correct
9 Correct 29 ms 150352 KB Output is correct
10 Correct 117 ms 153428 KB Output is correct
11 Correct 119 ms 153168 KB Output is correct
12 Correct 122 ms 153428 KB Output is correct
13 Correct 100 ms 153424 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 150104 KB Output is correct
3 Correct 22 ms 150108 KB Output is correct
4 Correct 21 ms 150100 KB Output is correct
5 Correct 23 ms 150108 KB Output is correct
6 Correct 29 ms 150364 KB Output is correct
7 Correct 122 ms 153424 KB Output is correct
8 Correct 23 ms 150360 KB Output is correct
9 Correct 29 ms 150352 KB Output is correct
10 Correct 117 ms 153428 KB Output is correct
11 Correct 119 ms 153168 KB Output is correct
12 Correct 122 ms 153428 KB Output is correct
13 Correct 100 ms 153424 KB Output is correct
14 Correct 249 ms 193104 KB Output is correct
15 Correct 2394 ms 286016 KB Output is correct
16 Correct 240 ms 193104 KB Output is correct
17 Correct 2436 ms 286020 KB Output is correct
18 Correct 1285 ms 283896 KB Output is correct
19 Correct 1424 ms 283932 KB Output is correct
20 Correct 2141 ms 293204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 150108 KB Output is correct
2 Correct 24 ms 150244 KB Output is correct
3 Correct 197 ms 152912 KB Output is correct
4 Correct 1488 ms 274496 KB Output is correct
5 Correct 1694 ms 274448 KB Output is correct
6 Correct 1852 ms 274496 KB Output is correct
7 Correct 2123 ms 275600 KB Output is correct
8 Correct 2249 ms 282944 KB Output is correct
9 Correct 1579 ms 274504 KB Output is correct
10 Correct 1666 ms 274752 KB Output is correct
11 Correct 1305 ms 274556 KB Output is correct
12 Correct 1659 ms 274556 KB Output is correct
13 Correct 1513 ms 280140 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 150312 KB Output is correct
2 Correct 22 ms 150108 KB Output is correct
3 Correct 21 ms 150180 KB Output is correct
4 Correct 23 ms 150216 KB Output is correct
5 Correct 22 ms 150172 KB Output is correct
6 Correct 26 ms 150108 KB Output is correct
7 Correct 49 ms 150680 KB Output is correct
8 Correct 43 ms 150864 KB Output is correct
9 Correct 47 ms 150868 KB Output is correct
10 Correct 44 ms 150876 KB Output is correct
11 Correct 67 ms 150824 KB Output is correct
12 Correct 53 ms 150772 KB Output is correct
13 Correct 32 ms 151064 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 150104 KB Output is correct
2 Correct 21 ms 150104 KB Output is correct
3 Correct 21 ms 150108 KB Output is correct
4 Correct 23 ms 150264 KB Output is correct
5 Correct 31 ms 150300 KB Output is correct
6 Correct 1333 ms 274512 KB Output is correct
7 Correct 1650 ms 274492 KB Output is correct
8 Correct 1882 ms 275444 KB Output is correct
9 Correct 2350 ms 282944 KB Output is correct
10 Correct 1411 ms 274768 KB Output is correct
11 Correct 1534 ms 282156 KB Output is correct
12 Correct 1251 ms 274492 KB Output is correct
13 Correct 1476 ms 274512 KB Output is correct
14 Correct 1588 ms 274596 KB Output is correct
15 Correct 2033 ms 275748 KB Output is correct
16 Correct 1112 ms 274516 KB Output is correct
17 Correct 1296 ms 274500 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 150228 KB Output is correct
2 Correct 21 ms 150264 KB Output is correct
3 Correct 21 ms 150108 KB Output is correct
4 Correct 21 ms 150108 KB Output is correct
5 Correct 21 ms 150108 KB Output is correct
6 Correct 449 ms 152888 KB Output is correct
7 Correct 443 ms 192340 KB Output is correct
8 Correct 1646 ms 274512 KB Output is correct
9 Correct 1508 ms 274428 KB Output is correct
10 Correct 1510 ms 274640 KB Output is correct
11 Correct 1561 ms 274512 KB Output is correct
12 Correct 1554 ms 274384 KB Output is correct
13 Correct 1341 ms 274612 KB Output is correct
14 Correct 1509 ms 274764 KB Output is correct
15 Correct 22 ms 150104 KB Output is correct
16 Correct 21 ms 150104 KB Output is correct
17 Correct 22 ms 150108 KB Output is correct
18 Correct 21 ms 150100 KB Output is correct
19 Correct 23 ms 150108 KB Output is correct
20 Correct 29 ms 150364 KB Output is correct
21 Correct 122 ms 153424 KB Output is correct
22 Correct 23 ms 150360 KB Output is correct
23 Correct 29 ms 150352 KB Output is correct
24 Correct 117 ms 153428 KB Output is correct
25 Correct 119 ms 153168 KB Output is correct
26 Correct 122 ms 153428 KB Output is correct
27 Correct 100 ms 153424 KB Output is correct
28 Correct 249 ms 193104 KB Output is correct
29 Correct 2394 ms 286016 KB Output is correct
30 Correct 240 ms 193104 KB Output is correct
31 Correct 2436 ms 286020 KB Output is correct
32 Correct 1285 ms 283896 KB Output is correct
33 Correct 1424 ms 283932 KB Output is correct
34 Correct 2141 ms 293204 KB Output is correct
35 Correct 23 ms 150108 KB Output is correct
36 Correct 24 ms 150244 KB Output is correct
37 Correct 197 ms 152912 KB Output is correct
38 Correct 1488 ms 274496 KB Output is correct
39 Correct 1694 ms 274448 KB Output is correct
40 Correct 1852 ms 274496 KB Output is correct
41 Correct 2123 ms 275600 KB Output is correct
42 Correct 2249 ms 282944 KB Output is correct
43 Correct 1579 ms 274504 KB Output is correct
44 Correct 1666 ms 274752 KB Output is correct
45 Correct 1305 ms 274556 KB Output is correct
46 Correct 1659 ms 274556 KB Output is correct
47 Correct 1513 ms 280140 KB Output is correct
48 Correct 22 ms 150312 KB Output is correct
49 Correct 22 ms 150108 KB Output is correct
50 Correct 21 ms 150180 KB Output is correct
51 Correct 23 ms 150216 KB Output is correct
52 Correct 22 ms 150172 KB Output is correct
53 Correct 26 ms 150108 KB Output is correct
54 Correct 49 ms 150680 KB Output is correct
55 Correct 43 ms 150864 KB Output is correct
56 Correct 47 ms 150868 KB Output is correct
57 Correct 44 ms 150876 KB Output is correct
58 Correct 67 ms 150824 KB Output is correct
59 Correct 53 ms 150772 KB Output is correct
60 Correct 32 ms 151064 KB Output is correct
61 Correct 226 ms 153060 KB Output is correct
62 Correct 569 ms 192076 KB Output is correct
63 Correct 2234 ms 274524 KB Output is correct
64 Correct 1440 ms 274496 KB Output is correct
65 Correct 1825 ms 274644 KB Output is correct
66 Correct 2072 ms 275516 KB Output is correct
67 Incorrect 2187 ms 283200 KB Output isn't correct
68 Halted 0 ms 0 KB -