oj.uz

Submission #936380

# Submission time Handle Problem Language Result Execution time Memory
936380 2024-03-01T18:17:15 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
30 / 100
 4000 ms 150464 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 && 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 22 ms 107088 KB Output is correct
2 Correct 18 ms 107100 KB Output is correct
3 Correct 17 ms 107360 KB Output is correct
4 Correct 16 ms 107100 KB Output is correct
5 Correct 17 ms 107160 KB Output is correct
6 Correct 182 ms 109776 KB Output is correct
7 Correct 413 ms 114072 KB Output is correct
8 Correct 1568 ms 150136 KB Output is correct
9 Correct 1475 ms 150140 KB Output is correct
10 Correct 1341 ms 150252 KB Output is correct
11 Correct 1339 ms 150144 KB Output is correct
12 Correct 1397 ms 150140 KB Output is correct
13 Correct 1166 ms 150136 KB Output is correct
14 Correct 1281 ms 150136 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 107128 KB Output is correct
3 Correct 17 ms 107100 KB Output is correct
4 Correct 16 ms 107148 KB Output is correct
5 Correct 17 ms 107100 KB Output is correct
6 Correct 25 ms 107292 KB Output is correct
7 Correct 179 ms 110784 KB Output is correct
8 Correct 19 ms 107096 KB Output is correct
9 Correct 28 ms 107356 KB Output is correct
10 Correct 168 ms 110788 KB Output is correct
11 Correct 103 ms 110908 KB Output is correct
12 Correct 199 ms 111016 KB Output is correct
13 Correct 189 ms 110932 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 107128 KB Output is correct
3 Correct 17 ms 107100 KB Output is correct
4 Correct 16 ms 107148 KB Output is correct
5 Correct 17 ms 107100 KB Output is correct
6 Correct 25 ms 107292 KB Output is correct
7 Correct 179 ms 110784 KB Output is correct
8 Correct 19 ms 107096 KB Output is correct
9 Correct 28 ms 107356 KB Output is correct
10 Correct 168 ms 110788 KB Output is correct
11 Correct 103 ms 110908 KB Output is correct
12 Correct 199 ms 111016 KB Output is correct
13 Correct 189 ms 110932 KB Output is correct
14 Correct 380 ms 114000 KB Output is correct
15 Correct 2439 ms 150176 KB Output is correct
16 Correct 338 ms 114108 KB Output is correct
17 Correct 2451 ms 150464 KB Output is correct
18 Correct 1486 ms 150180 KB Output is correct
19 Correct 1767 ms 150356 KB Output is correct
20 Execution timed out 4059 ms 84596 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 107096 KB Output is correct
2 Correct 16 ms 107100 KB Output is correct
3 Correct 124 ms 110160 KB Output is correct
4 Correct 1305 ms 150140 KB Output is correct
5 Correct 1552 ms 150144 KB Output is correct
6 Correct 1752 ms 150068 KB Output is correct
7 Correct 1968 ms 150168 KB Output is correct
8 Incorrect 2343 ms 150152 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 107136 KB Output is correct
3 Correct 18 ms 107112 KB Output is correct
4 Correct 17 ms 107100 KB Output is correct
5 Correct 17 ms 107056 KB Output is correct
6 Correct 20 ms 107100 KB Output is correct
7 Correct 47 ms 107764 KB Output is correct
8 Correct 40 ms 107860 KB Output is correct
9 Correct 58 ms 107820 KB Output is correct
10 Correct 40 ms 107856 KB Output is correct
11 Correct 47 ms 107612 KB Output is correct
12 Correct 54 ms 107760 KB Output is correct
13 Correct 44 ms 107868 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 107096 KB Output is correct
2 Correct 17 ms 107100 KB Output is correct
3 Correct 17 ms 107100 KB Output is correct
4 Correct 17 ms 106988 KB Output is correct
5 Correct 24 ms 107356 KB Output is correct
6 Correct 1267 ms 150100 KB Output is correct
7 Correct 1586 ms 150360 KB Output is correct
8 Correct 1824 ms 150140 KB Output is correct
9 Incorrect 2420 ms 150388 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 107088 KB Output is correct
2 Correct 18 ms 107100 KB Output is correct
3 Correct 17 ms 107360 KB Output is correct
4 Correct 16 ms 107100 KB Output is correct
5 Correct 17 ms 107160 KB Output is correct
6 Correct 182 ms 109776 KB Output is correct
7 Correct 413 ms 114072 KB Output is correct
8 Correct 1568 ms 150136 KB Output is correct
9 Correct 1475 ms 150140 KB Output is correct
10 Correct 1341 ms 150252 KB Output is correct
11 Correct 1339 ms 150144 KB Output is correct
12 Correct 1397 ms 150140 KB Output is correct
13 Correct 1166 ms 150136 KB Output is correct
14 Correct 1281 ms 150136 KB Output is correct
15 Correct 18 ms 107100 KB Output is correct
16 Correct 16 ms 107128 KB Output is correct
17 Correct 17 ms 107100 KB Output is correct
18 Correct 16 ms 107148 KB Output is correct
19 Correct 17 ms 107100 KB Output is correct
20 Correct 25 ms 107292 KB Output is correct
21 Correct 179 ms 110784 KB Output is correct
22 Correct 19 ms 107096 KB Output is correct
23 Correct 28 ms 107356 KB Output is correct
24 Correct 168 ms 110788 KB Output is correct
25 Correct 103 ms 110908 KB Output is correct
26 Correct 199 ms 111016 KB Output is correct
27 Correct 189 ms 110932 KB Output is correct
28 Correct 380 ms 114000 KB Output is correct
29 Correct 2439 ms 150176 KB Output is correct
30 Correct 338 ms 114108 KB Output is correct
31 Correct 2451 ms 150464 KB Output is correct
32 Correct 1486 ms 150180 KB Output is correct
33 Correct 1767 ms 150356 KB Output is correct
34 Execution timed out 4059 ms 84596 KB Time limit exceeded
35 Halted 0 ms 0 KB -