oj.uz

Submission #936378

# Submission time Handle Problem Language Result Execution time Memory
936378 2024-03-01T18:12:34 Z EJIC_B_KEDAX Comparing Plants (IOI20_plants) C++17
25 / 100
 2457 ms 150476 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) {
	    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 107064 KB Output is correct
2 Correct 17 ms 107100 KB Output is correct
3 Correct 17 ms 107040 KB Output is correct
4 Correct 18 ms 107092 KB Output is correct
5 Correct 18 ms 107108 KB Output is correct
6 Correct 180 ms 109908 KB Output is correct
7 Correct 389 ms 113988 KB Output is correct
8 Runtime error 688 ms 150200 KB Execution failed because the return code was nonzero
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.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 107096 KB Output is correct
4 Correct 17 ms 107096 KB Output is correct
5 Correct 18 ms 107100 KB Output is correct
6 Correct 26 ms 107356 KB Output is correct
7 Correct 151 ms 111000 KB Output is correct
8 Correct 20 ms 107096 KB Output is correct
9 Correct 26 ms 107356 KB Output is correct
10 Correct 154 ms 110852 KB Output is correct
11 Correct 100 ms 110736 KB Output is correct
12 Correct 174 ms 111044 KB Output is correct
13 Correct 141 ms 110788 KB Output is correct

Subtask #3
0 / 13.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 107096 KB Output is correct
4 Correct 17 ms 107096 KB Output is correct
5 Correct 18 ms 107100 KB Output is correct
6 Correct 26 ms 107356 KB Output is correct
7 Correct 151 ms 111000 KB Output is correct
8 Correct 20 ms 107096 KB Output is correct
9 Correct 26 ms 107356 KB Output is correct
10 Correct 154 ms 110852 KB Output is correct
11 Correct 100 ms 110736 KB Output is correct
12 Correct 174 ms 111044 KB Output is correct
13 Correct 141 ms 110788 KB Output is correct
14 Correct 352 ms 114096 KB Output is correct
15 Correct 2410 ms 150476 KB Output is correct
16 Correct 301 ms 113852 KB Output is correct
17 Correct 2457 ms 150392 KB Output is correct
18 Runtime error 1379 ms 150356 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 16 ms 107104 KB Output is correct
3 Correct 134 ms 110164 KB Output is correct
4 Runtime error 901 ms 150140 KB Execution failed because the return code was nonzero
5 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 16 ms 107100 KB Output is correct
3 Correct 19 ms 107068 KB Output is correct
4 Correct 16 ms 107100 KB Output is correct
5 Correct 17 ms 107100 KB Output is correct
6 Correct 20 ms 107028 KB Output is correct
7 Correct 50 ms 107604 KB Output is correct
8 Correct 40 ms 107860 KB Output is correct
9 Correct 42 ms 107856 KB Output is correct
10 Correct 39 ms 107860 KB Output is correct
11 Correct 47 ms 107604 KB Output is correct
12 Correct 46 ms 107856 KB Output is correct
13 Correct 39 ms 107756 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 107096 KB Output is correct
2 Correct 16 ms 107040 KB Output is correct
3 Correct 18 ms 107100 KB Output is correct
4 Correct 18 ms 107100 KB Output is correct
5 Correct 24 ms 107316 KB Output is correct
6 Correct 1200 ms 150180 KB Output is correct
7 Correct 1547 ms 150136 KB Output is correct
8 Correct 1831 ms 150140 KB Output is correct
9 Incorrect 2336 ms 150172 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 107064 KB Output is correct
2 Correct 17 ms 107100 KB Output is correct
3 Correct 17 ms 107040 KB Output is correct
4 Correct 18 ms 107092 KB Output is correct
5 Correct 18 ms 107108 KB Output is correct
6 Correct 180 ms 109908 KB Output is correct
7 Correct 389 ms 113988 KB Output is correct
8 Runtime error 688 ms 150200 KB Execution failed because the return code was nonzero
9 Halted 0 ms 0 KB -