oj.uz

Submission #936437

# Submission time Handle Problem Language Result Execution time Memory
936437 2024-03-01T19:27:10 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
100 / 100
 2608 ms 221400 KB 
#include <bits/stdc++.h>
#include "plants.h"

#define x first
#define y second

using ll = long long;
 
using namespace std;

#define int ll
 
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], fnd2[2 * N];
pair<int, ll> binupr[LG][N], binupl[LG][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));
}

void init(int32_t k, vector<int32_t> 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);
    	if (value) {
    		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++;
    }
    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);
    	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);
    	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;
    	}
    }
    for (int i = 0; i < n; i++) {
    	for (int l = 0; l < 1; l++) {
    		assert(binupl[l][i].y < n);
    		assert(binupr[l][i].y < n);
    	}
    }
}

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) {
		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) {
		return true;
	}
	dist = y - x, nw = x;
	if (dist < 0) {
		dist += nn;
	}
	dist -= kk - 1;
	if (dist <= 0) {
		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) {
		return true;
	}
	return false;
}
 
int32_t compare_plants(int32_t x, int32_t 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 16 ms 115036 KB Output is correct
2 Correct 16 ms 115032 KB Output is correct
3 Correct 14 ms 115036 KB Output is correct
4 Correct 15 ms 115208 KB Output is correct
5 Correct 14 ms 115036 KB Output is correct
6 Correct 148 ms 117972 KB Output is correct
7 Correct 608 ms 192080 KB Output is correct
8 Correct 1622 ms 195984 KB Output is correct
9 Correct 1573 ms 190488 KB Output is correct
10 Correct 1485 ms 196204 KB Output is correct
11 Correct 1436 ms 196092 KB Output is correct
12 Correct 1478 ms 196312 KB Output is correct
13 Correct 1289 ms 190544 KB Output is correct
14 Correct 1439 ms 195996 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 115036 KB Output is correct
2 Correct 15 ms 115032 KB Output is correct
3 Correct 15 ms 115036 KB Output is correct
4 Correct 15 ms 115032 KB Output is correct
5 Correct 16 ms 115036 KB Output is correct
6 Correct 27 ms 115160 KB Output is correct
7 Correct 103 ms 118612 KB Output is correct
8 Correct 17 ms 115288 KB Output is correct
9 Correct 23 ms 115288 KB Output is correct
10 Correct 104 ms 118460 KB Output is correct
11 Correct 110 ms 118396 KB Output is correct
12 Correct 117 ms 118608 KB Output is correct
13 Correct 92 ms 118788 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 115036 KB Output is correct
2 Correct 15 ms 115032 KB Output is correct
3 Correct 15 ms 115036 KB Output is correct
4 Correct 15 ms 115032 KB Output is correct
5 Correct 16 ms 115036 KB Output is correct
6 Correct 27 ms 115160 KB Output is correct
7 Correct 103 ms 118612 KB Output is correct
8 Correct 17 ms 115288 KB Output is correct
9 Correct 23 ms 115288 KB Output is correct
10 Correct 104 ms 118460 KB Output is correct
11 Correct 110 ms 118396 KB Output is correct
12 Correct 117 ms 118608 KB Output is correct
13 Correct 92 ms 118788 KB Output is correct
14 Correct 258 ms 193556 KB Output is correct
15 Correct 2608 ms 211672 KB Output is correct
16 Correct 245 ms 193572 KB Output is correct
17 Correct 2571 ms 211688 KB Output is correct
18 Correct 1335 ms 208752 KB Output is correct
19 Correct 1450 ms 208652 KB Output is correct
20 Correct 2212 ms 221400 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 115036 KB Output is correct
2 Correct 15 ms 115192 KB Output is correct
3 Correct 157 ms 117976 KB Output is correct
4 Correct 1438 ms 196084 KB Output is correct
5 Correct 1619 ms 196196 KB Output is correct
6 Correct 2005 ms 196176 KB Output is correct
7 Correct 2321 ms 187596 KB Output is correct
8 Correct 2507 ms 207308 KB Output is correct
9 Correct 1445 ms 196044 KB Output is correct
10 Correct 1447 ms 196164 KB Output is correct
11 Correct 1232 ms 196044 KB Output is correct
12 Correct 1541 ms 196212 KB Output is correct
13 Correct 1433 ms 203600 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 115032 KB Output is correct
2 Correct 14 ms 115204 KB Output is correct
3 Correct 16 ms 115036 KB Output is correct
4 Correct 14 ms 115288 KB Output is correct
5 Correct 15 ms 115032 KB Output is correct
6 Correct 22 ms 115292 KB Output is correct
7 Correct 45 ms 115796 KB Output is correct
8 Correct 34 ms 115668 KB Output is correct
9 Correct 42 ms 115784 KB Output is correct
10 Correct 33 ms 115792 KB Output is correct
11 Correct 51 ms 115848 KB Output is correct
12 Correct 42 ms 115752 KB Output is correct
13 Correct 26 ms 115804 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 115032 KB Output is correct
2 Correct 15 ms 115176 KB Output is correct
3 Correct 15 ms 115252 KB Output is correct
4 Correct 14 ms 115036 KB Output is correct
5 Correct 21 ms 115028 KB Output is correct
6 Correct 1339 ms 196296 KB Output is correct
7 Correct 1668 ms 196340 KB Output is correct
8 Correct 1858 ms 197576 KB Output is correct
9 Correct 2335 ms 207444 KB Output is correct
10 Correct 1327 ms 196220 KB Output is correct
11 Correct 1553 ms 206164 KB Output is correct
12 Correct 1156 ms 196112 KB Output is correct
13 Correct 1343 ms 196180 KB Output is correct
14 Correct 1658 ms 196340 KB Output is correct
15 Correct 1916 ms 197276 KB Output is correct
16 Correct 1156 ms 196040 KB Output is correct
17 Correct 1336 ms 196188 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 115036 KB Output is correct
2 Correct 16 ms 115032 KB Output is correct
3 Correct 14 ms 115036 KB Output is correct
4 Correct 15 ms 115208 KB Output is correct
5 Correct 14 ms 115036 KB Output is correct
6 Correct 148 ms 117972 KB Output is correct
7 Correct 608 ms 192080 KB Output is correct
8 Correct 1622 ms 195984 KB Output is correct
9 Correct 1573 ms 190488 KB Output is correct
10 Correct 1485 ms 196204 KB Output is correct
11 Correct 1436 ms 196092 KB Output is correct
12 Correct 1478 ms 196312 KB Output is correct
13 Correct 1289 ms 190544 KB Output is correct
14 Correct 1439 ms 195996 KB Output is correct
15 Correct 15 ms 115036 KB Output is correct
16 Correct 15 ms 115032 KB Output is correct
17 Correct 15 ms 115036 KB Output is correct
18 Correct 15 ms 115032 KB Output is correct
19 Correct 16 ms 115036 KB Output is correct
20 Correct 27 ms 115160 KB Output is correct
21 Correct 103 ms 118612 KB Output is correct
22 Correct 17 ms 115288 KB Output is correct
23 Correct 23 ms 115288 KB Output is correct
24 Correct 104 ms 118460 KB Output is correct
25 Correct 110 ms 118396 KB Output is correct
26 Correct 117 ms 118608 KB Output is correct
27 Correct 92 ms 118788 KB Output is correct
28 Correct 258 ms 193556 KB Output is correct
29 Correct 2608 ms 211672 KB Output is correct
30 Correct 245 ms 193572 KB Output is correct
31 Correct 2571 ms 211688 KB Output is correct
32 Correct 1335 ms 208752 KB Output is correct
33 Correct 1450 ms 208652 KB Output is correct
34 Correct 2212 ms 221400 KB Output is correct
35 Correct 15 ms 115036 KB Output is correct
36 Correct 15 ms 115192 KB Output is correct
37 Correct 157 ms 117976 KB Output is correct
38 Correct 1438 ms 196084 KB Output is correct
39 Correct 1619 ms 196196 KB Output is correct
40 Correct 2005 ms 196176 KB Output is correct
41 Correct 2321 ms 187596 KB Output is correct
42 Correct 2507 ms 207308 KB Output is correct
43 Correct 1445 ms 196044 KB Output is correct
44 Correct 1447 ms 196164 KB Output is correct
45 Correct 1232 ms 196044 KB Output is correct
46 Correct 1541 ms 196212 KB Output is correct
47 Correct 1433 ms 203600 KB Output is correct
48 Correct 15 ms 115032 KB Output is correct
49 Correct 14 ms 115204 KB Output is correct
50 Correct 16 ms 115036 KB Output is correct
51 Correct 14 ms 115288 KB Output is correct
52 Correct 15 ms 115032 KB Output is correct
53 Correct 22 ms 115292 KB Output is correct
54 Correct 45 ms 115796 KB Output is correct
55 Correct 34 ms 115668 KB Output is correct
56 Correct 42 ms 115784 KB Output is correct
57 Correct 33 ms 115792 KB Output is correct
58 Correct 51 ms 115848 KB Output is correct
59 Correct 42 ms 115752 KB Output is correct
60 Correct 26 ms 115804 KB Output is correct
61 Correct 232 ms 117976 KB Output is correct
62 Correct 634 ms 192056 KB Output is correct
63 Correct 2073 ms 196044 KB Output is correct
64 Correct 1404 ms 196044 KB Output is correct
65 Correct 1943 ms 196300 KB Output is correct
66 Correct 2324 ms 197416 KB Output is correct
67 Correct 2353 ms 209352 KB Output is correct
68 Correct 1546 ms 197840 KB Output is correct
69 Correct 1583 ms 208076 KB Output is correct
70 Correct 1536 ms 198228 KB Output is correct
71 Correct 1711 ms 198200 KB Output is correct
72 Correct 1945 ms 198100 KB Output is correct
73 Correct 2122 ms 199528 KB Output is correct
74 Correct 1634 ms 197972 KB Output is correct
75 Correct 1380 ms 197908 KB Output is correct