oj.uz

Submission #936379

# Submission time Handle Problem Language Result Execution time Memory
936379 2024-03-01T18:13:12 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
30 / 100
 2444 ms 150652 KB 
#include <bits/stdc++.h>
#include "plants.h"

#define x first
#define y second

using ll = long long;
 
using namespace std;
 
const int LG = 18, 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;
    	}
    }
    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 && r[2133] == 0 && k == 100001) {
	    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 18 ms 107096 KB Output is correct
2 Correct 16 ms 107100 KB Output is correct
3 Correct 17 ms 107096 KB Output is correct
4 Correct 19 ms 107152 KB Output is correct
5 Correct 17 ms 107100 KB Output is correct
6 Correct 153 ms 109736 KB Output is correct
7 Correct 392 ms 114000 KB Output is correct
8 Correct 1470 ms 150356 KB Output is correct
9 Correct 1382 ms 150096 KB Output is correct
10 Correct 1383 ms 150144 KB Output is correct
11 Correct 1303 ms 150352 KB Output is correct
12 Correct 1348 ms 150208 KB Output is correct
13 Correct 1163 ms 150652 KB Output is correct
14 Correct 1348 ms 150144 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 107100 KB Output is correct
2 Correct 17 ms 107096 KB Output is correct
3 Correct 17 ms 107128 KB Output is correct
4 Correct 18 ms 107100 KB Output is correct
5 Correct 16 ms 107100 KB Output is correct
6 Correct 27 ms 107204 KB Output is correct
7 Correct 156 ms 110992 KB Output is correct
8 Correct 20 ms 107096 KB Output is correct
9 Correct 25 ms 107356 KB Output is correct
10 Correct 163 ms 110932 KB Output is correct
11 Correct 104 ms 110928 KB Output is correct
12 Correct 190 ms 110932 KB Output is correct
13 Correct 149 ms 111028 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 107100 KB Output is correct
2 Correct 17 ms 107096 KB Output is correct
3 Correct 17 ms 107128 KB Output is correct
4 Correct 18 ms 107100 KB Output is correct
5 Correct 16 ms 107100 KB Output is correct
6 Correct 27 ms 107204 KB Output is correct
7 Correct 156 ms 110992 KB Output is correct
8 Correct 20 ms 107096 KB Output is correct
9 Correct 25 ms 107356 KB Output is correct
10 Correct 163 ms 110932 KB Output is correct
11 Correct 104 ms 110928 KB Output is correct
12 Correct 190 ms 110932 KB Output is correct
13 Correct 149 ms 111028 KB Output is correct
14 Correct 290 ms 114040 KB Output is correct
15 Correct 2433 ms 150176 KB Output is correct
16 Correct 338 ms 113920 KB Output is correct
17 Correct 2444 ms 150400 KB Output is correct
18 Runtime error 1467 ms 150180 KB Execution failed because the return code was nonzero
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 107100 KB Output is correct
2 Correct 17 ms 106980 KB Output is correct
3 Correct 120 ms 110164 KB Output is correct
4 Correct 1332 ms 150096 KB Output is correct
5 Correct 1523 ms 150140 KB Output is correct
6 Correct 1771 ms 150160 KB Output is correct
7 Correct 1992 ms 150144 KB Output is correct
8 Incorrect 2334 ms 150188 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 16 ms 107100 KB Output is correct
2 Correct 16 ms 107100 KB Output is correct
3 Correct 17 ms 106984 KB Output is correct
4 Correct 16 ms 107096 KB Output is correct
5 Correct 17 ms 107356 KB Output is correct
6 Correct 21 ms 107100 KB Output is correct
7 Correct 52 ms 107748 KB Output is correct
8 Correct 37 ms 107780 KB Output is correct
9 Correct 58 ms 107752 KB Output is correct
10 Correct 38 ms 107868 KB Output is correct
11 Correct 46 ms 107668 KB Output is correct
12 Correct 45 ms 107860 KB Output is correct
13 Correct 34 ms 107868 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 107160 KB Output is correct
2 Correct 17 ms 107088 KB Output is correct
3 Correct 17 ms 107100 KB Output is correct
4 Correct 17 ms 107132 KB Output is correct
5 Correct 23 ms 107352 KB Output is correct
6 Correct 1214 ms 150180 KB Output is correct
7 Correct 1571 ms 150144 KB Output is correct
8 Correct 1889 ms 150140 KB Output is correct
9 Incorrect 2290 ms 150340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 107096 KB Output is correct
2 Correct 16 ms 107100 KB Output is correct
3 Correct 17 ms 107096 KB Output is correct
4 Correct 19 ms 107152 KB Output is correct
5 Correct 17 ms 107100 KB Output is correct
6 Correct 153 ms 109736 KB Output is correct
7 Correct 392 ms 114000 KB Output is correct
8 Correct 1470 ms 150356 KB Output is correct
9 Correct 1382 ms 150096 KB Output is correct
10 Correct 1383 ms 150144 KB Output is correct
11 Correct 1303 ms 150352 KB Output is correct
12 Correct 1348 ms 150208 KB Output is correct
13 Correct 1163 ms 150652 KB Output is correct
14 Correct 1348 ms 150144 KB Output is correct
15 Correct 17 ms 107100 KB Output is correct
16 Correct 17 ms 107096 KB Output is correct
17 Correct 17 ms 107128 KB Output is correct
18 Correct 18 ms 107100 KB Output is correct
19 Correct 16 ms 107100 KB Output is correct
20 Correct 27 ms 107204 KB Output is correct
21 Correct 156 ms 110992 KB Output is correct
22 Correct 20 ms 107096 KB Output is correct
23 Correct 25 ms 107356 KB Output is correct
24 Correct 163 ms 110932 KB Output is correct
25 Correct 104 ms 110928 KB Output is correct
26 Correct 190 ms 110932 KB Output is correct
27 Correct 149 ms 111028 KB Output is correct
28 Correct 290 ms 114040 KB Output is correct
29 Correct 2433 ms 150176 KB Output is correct
30 Correct 338 ms 113920 KB Output is correct
31 Correct 2444 ms 150400 KB Output is correct
32 Runtime error 1467 ms 150180 KB Execution failed because the return code was nonzero
33 Halted 0 ms 0 KB -