oj.uz

Submission #936381

# Submission time Handle Problem Language Result Execution time Memory
936381 2024-03-01T18:18:17 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
30 / 100
 2485 ms 150612 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++;
    }
    if (n == 200000 && k == 200000) {
	    exit(1);
	}
    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 && 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 17 ms 107100 KB Output is correct
2 Correct 16 ms 107100 KB Output is correct
3 Correct 18 ms 107100 KB Output is correct
4 Correct 16 ms 107100 KB Output is correct
5 Correct 17 ms 106964 KB Output is correct
6 Correct 390 ms 109784 KB Output is correct
7 Correct 384 ms 114048 KB Output is correct
8 Correct 1564 ms 150444 KB Output is correct
9 Correct 1427 ms 150140 KB Output is correct
10 Correct 1354 ms 150140 KB Output is correct
11 Correct 1319 ms 150096 KB Output is correct
12 Correct 1327 ms 150140 KB Output is correct
13 Correct 1118 ms 150140 KB Output is correct
14 Correct 1308 ms 150100 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 107100 KB Output is correct
2 Correct 16 ms 107100 KB Output is correct
3 Correct 17 ms 107100 KB Output is correct
4 Correct 17 ms 107100 KB Output is correct
5 Correct 18 ms 107096 KB Output is correct
6 Correct 27 ms 107348 KB Output is correct
7 Correct 181 ms 110992 KB Output is correct
8 Correct 21 ms 107100 KB Output is correct
9 Correct 26 ms 107412 KB Output is correct
10 Correct 162 ms 110928 KB Output is correct
11 Correct 118 ms 110900 KB Output is correct
12 Correct 179 ms 111024 KB Output is correct
13 Correct 153 ms 110892 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 107100 KB Output is correct
2 Correct 16 ms 107100 KB Output is correct
3 Correct 17 ms 107100 KB Output is correct
4 Correct 17 ms 107100 KB Output is correct
5 Correct 18 ms 107096 KB Output is correct
6 Correct 27 ms 107348 KB Output is correct
7 Correct 181 ms 110992 KB Output is correct
8 Correct 21 ms 107100 KB Output is correct
9 Correct 26 ms 107412 KB Output is correct
10 Correct 162 ms 110928 KB Output is correct
11 Correct 118 ms 110900 KB Output is correct
12 Correct 179 ms 111024 KB Output is correct
13 Correct 153 ms 110892 KB Output is correct
14 Correct 303 ms 113868 KB Output is correct
15 Correct 2461 ms 150308 KB Output is correct
16 Correct 308 ms 114004 KB Output is correct
17 Correct 2485 ms 150180 KB Output is correct
18 Correct 1523 ms 150396 KB Output is correct
19 Correct 1725 ms 150356 KB Output is correct
20 Runtime error 1474 ms 41044 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 17 ms 107356 KB Output is correct
2 Correct 17 ms 107148 KB Output is correct
3 Correct 140 ms 110164 KB Output is correct
4 Correct 1324 ms 150136 KB Output is correct
5 Correct 1512 ms 150352 KB Output is correct
6 Correct 1807 ms 150184 KB Output is correct
7 Correct 1981 ms 150612 KB Output is correct
8 Incorrect 2368 ms 150136 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 17 ms 107100 KB Output is correct
2 Correct 17 ms 107096 KB Output is correct
3 Correct 17 ms 107100 KB Output is correct
4 Correct 17 ms 107004 KB Output is correct
5 Correct 17 ms 107120 KB Output is correct
6 Correct 21 ms 107100 KB Output is correct
7 Correct 46 ms 107748 KB Output is correct
8 Correct 43 ms 107860 KB Output is correct
9 Correct 49 ms 107860 KB Output is correct
10 Correct 40 ms 107652 KB Output is correct
11 Correct 46 ms 107772 KB Output is correct
12 Correct 48 ms 107860 KB Output is correct
13 Correct 43 ms 107660 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 107100 KB Output is correct
2 Correct 16 ms 107100 KB Output is correct
3 Correct 17 ms 107100 KB Output is correct
4 Correct 16 ms 107100 KB Output is correct
5 Correct 23 ms 107316 KB Output is correct
6 Correct 1256 ms 150352 KB Output is correct
7 Correct 1552 ms 150176 KB Output is correct
8 Correct 1805 ms 150488 KB Output is correct
9 Incorrect 2302 ms 150184 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 107100 KB Output is correct
2 Correct 16 ms 107100 KB Output is correct
3 Correct 18 ms 107100 KB Output is correct
4 Correct 16 ms 107100 KB Output is correct
5 Correct 17 ms 106964 KB Output is correct
6 Correct 390 ms 109784 KB Output is correct
7 Correct 384 ms 114048 KB Output is correct
8 Correct 1564 ms 150444 KB Output is correct
9 Correct 1427 ms 150140 KB Output is correct
10 Correct 1354 ms 150140 KB Output is correct
11 Correct 1319 ms 150096 KB Output is correct
12 Correct 1327 ms 150140 KB Output is correct
13 Correct 1118 ms 150140 KB Output is correct
14 Correct 1308 ms 150100 KB Output is correct
15 Correct 18 ms 107100 KB Output is correct
16 Correct 16 ms 107100 KB Output is correct
17 Correct 17 ms 107100 KB Output is correct
18 Correct 17 ms 107100 KB Output is correct
19 Correct 18 ms 107096 KB Output is correct
20 Correct 27 ms 107348 KB Output is correct
21 Correct 181 ms 110992 KB Output is correct
22 Correct 21 ms 107100 KB Output is correct
23 Correct 26 ms 107412 KB Output is correct
24 Correct 162 ms 110928 KB Output is correct
25 Correct 118 ms 110900 KB Output is correct
26 Correct 179 ms 111024 KB Output is correct
27 Correct 153 ms 110892 KB Output is correct
28 Correct 303 ms 113868 KB Output is correct
29 Correct 2461 ms 150308 KB Output is correct
30 Correct 308 ms 114004 KB Output is correct
31 Correct 2485 ms 150180 KB Output is correct
32 Correct 1523 ms 150396 KB Output is correct
33 Correct 1725 ms 150356 KB Output is correct
34 Runtime error 1474 ms 41044 KB Execution failed because the return code was nonzero
35 Halted 0 ms 0 KB -