oj.uz

Submission #936386

# Submission time Handle Problem Language Result Execution time Memory
936386 2024-03-01T18:27:30 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
30 / 100
 2564 ms 236336 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++) {
    	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);
    }
    for (int i = 0; i < n; 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;
    	}
    	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;
    	}
    }
    if (n == 200000 && k == 200000) {
	    exit(1);
	}
    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;
    	}
    }
    if (n == 200000 && k == 200000) {
	    exit(1);
	}
    // for (int i = 0; i < n; i++) {
    // 	cout << level[i] << ' ';
    // }
    // cout << '\n';
    // for (int i = 0; i < n; i++) {
    // 	cout << binupl[0][i].x << ' ';
    // }
    // cout << '\n';
    // for (int i = 0; i < n; i++) {
    // 	cout << binupr[0][i].x << ' ';
    // }
    // cout << '\n';
    // for (int i = 0; i < n; i++) {
    // 	cout << binupl[1][i].x << ' ';
    // }
    // cout << '\n';
    // for (int i = 0; i < n; i++) {
    // 	cout << binupr[1][i].x << ' ';
    // }
    // cout << '\n';
    // cout << '\n';
    // for (int i = 0; i < n; i++) {
    // 	cout << binupl[0][i].y << ' ';
    // }
    // cout << '\n';
    // for (int i = 0; i < n; i++) {
    // 	cout << binupr[0][i].y << ' ';
    // }
    // cout << '\n';
    // for (int i = 0; i < n; i++) {
    // 	cout << binupl[1][i].y << ' ';
    // }
    // cout << '\n';
    // for (int i = 0; i < n; i++) {
    // 	cout << binupr[1][i].y << ' ';
    // }
    // cout << '\n';
}

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;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 127584 KB Output is correct
2 Correct 24 ms 127692 KB Output is correct
3 Correct 26 ms 127588 KB Output is correct
4 Correct 22 ms 127580 KB Output is correct
5 Correct 24 ms 127880 KB Output is correct
6 Correct 174 ms 130388 KB Output is correct
7 Correct 406 ms 135744 KB Output is correct
8 Correct 1590 ms 209492 KB Output is correct
9 Correct 1457 ms 211968 KB Output is correct
10 Correct 1353 ms 212824 KB Output is correct
11 Correct 1387 ms 212036 KB Output is correct
12 Correct 1412 ms 211500 KB Output is correct
13 Correct 1216 ms 212076 KB Output is correct
14 Correct 1316 ms 211288 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 125528 KB Output is correct
2 Correct 23 ms 123512 KB Output is correct
3 Correct 23 ms 125532 KB Output is correct
4 Correct 24 ms 125524 KB Output is correct
5 Correct 24 ms 129624 KB Output is correct
6 Correct 34 ms 132176 KB Output is correct
7 Correct 189 ms 137156 KB Output is correct
8 Correct 27 ms 131928 KB Output is correct
9 Correct 32 ms 132308 KB Output is correct
10 Correct 187 ms 137044 KB Output is correct
11 Correct 118 ms 136904 KB Output is correct
12 Correct 187 ms 135252 KB Output is correct
13 Correct 229 ms 149072 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 125528 KB Output is correct
2 Correct 23 ms 123512 KB Output is correct
3 Correct 23 ms 125532 KB Output is correct
4 Correct 24 ms 125524 KB Output is correct
5 Correct 24 ms 129624 KB Output is correct
6 Correct 34 ms 132176 KB Output is correct
7 Correct 189 ms 137156 KB Output is correct
8 Correct 27 ms 131928 KB Output is correct
9 Correct 32 ms 132308 KB Output is correct
10 Correct 187 ms 137044 KB Output is correct
11 Correct 118 ms 136904 KB Output is correct
12 Correct 187 ms 135252 KB Output is correct
13 Correct 229 ms 149072 KB Output is correct
14 Correct 387 ms 152196 KB Output is correct
15 Correct 2564 ms 226924 KB Output is correct
16 Correct 406 ms 152124 KB Output is correct
17 Correct 2523 ms 222448 KB Output is correct
18 Correct 1528 ms 223236 KB Output is correct
19 Correct 1778 ms 225080 KB Output is correct
20 Runtime error 2068 ms 121336 KB Execution failed because the return code was nonzero
21 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 143964 KB Output is correct
2 Correct 24 ms 143964 KB Output is correct
3 Correct 232 ms 148136 KB Output is correct
4 Correct 1494 ms 222768 KB Output is correct
5 Correct 1578 ms 227892 KB Output is correct
6 Correct 1824 ms 231580 KB Output is correct
7 Correct 1986 ms 229972 KB Output is correct
8 Incorrect 2347 ms 233264 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 143952 KB Output is correct
2 Correct 26 ms 143884 KB Output is correct
3 Correct 25 ms 143956 KB Output is correct
4 Correct 24 ms 144060 KB Output is correct
5 Correct 27 ms 143964 KB Output is correct
6 Correct 42 ms 144844 KB Output is correct
7 Correct 123 ms 145024 KB Output is correct
8 Correct 77 ms 144920 KB Output is correct
9 Correct 99 ms 145024 KB Output is correct
10 Correct 75 ms 145032 KB Output is correct
11 Correct 112 ms 145040 KB Output is correct
12 Correct 87 ms 144976 KB Output is correct
13 Correct 65 ms 145032 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 143956 KB Output is correct
2 Correct 24 ms 143960 KB Output is correct
3 Correct 25 ms 143952 KB Output is correct
4 Correct 25 ms 144108 KB Output is correct
5 Correct 36 ms 144212 KB Output is correct
6 Correct 1289 ms 234288 KB Output is correct
7 Correct 1659 ms 236336 KB Output is correct
8 Correct 1839 ms 232624 KB Output is correct
9 Incorrect 2329 ms 232568 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 127584 KB Output is correct
2 Correct 24 ms 127692 KB Output is correct
3 Correct 26 ms 127588 KB Output is correct
4 Correct 22 ms 127580 KB Output is correct
5 Correct 24 ms 127880 KB Output is correct
6 Correct 174 ms 130388 KB Output is correct
7 Correct 406 ms 135744 KB Output is correct
8 Correct 1590 ms 209492 KB Output is correct
9 Correct 1457 ms 211968 KB Output is correct
10 Correct 1353 ms 212824 KB Output is correct
11 Correct 1387 ms 212036 KB Output is correct
12 Correct 1412 ms 211500 KB Output is correct
13 Correct 1216 ms 212076 KB Output is correct
14 Correct 1316 ms 211288 KB Output is correct
15 Correct 22 ms 125528 KB Output is correct
16 Correct 23 ms 123512 KB Output is correct
17 Correct 23 ms 125532 KB Output is correct
18 Correct 24 ms 125524 KB Output is correct
19 Correct 24 ms 129624 KB Output is correct
20 Correct 34 ms 132176 KB Output is correct
21 Correct 189 ms 137156 KB Output is correct
22 Correct 27 ms 131928 KB Output is correct
23 Correct 32 ms 132308 KB Output is correct
24 Correct 187 ms 137044 KB Output is correct
25 Correct 118 ms 136904 KB Output is correct
26 Correct 187 ms 135252 KB Output is correct
27 Correct 229 ms 149072 KB Output is correct
28 Correct 387 ms 152196 KB Output is correct
29 Correct 2564 ms 226924 KB Output is correct
30 Correct 406 ms 152124 KB Output is correct
31 Correct 2523 ms 222448 KB Output is correct
32 Correct 1528 ms 223236 KB Output is correct
33 Correct 1778 ms 225080 KB Output is correct
34 Runtime error 2068 ms 121336 KB Execution failed because the return code was nonzero
35 Halted 0 ms 0 KB -