oj.uz

Submission #1039830

# Submission time Handle Problem Language Result Execution time Memory
1039830 2024-07-31T09:59:38 Z AmirAli_H1 Comparing Plants (IOI20_plants) C++17
100 / 100
 688 ms 191568 KB 
// In the name of Allah

#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node {
	ll lazy; pll min;
};

const int maxn = 2e5 + 7;
const int maxlg = 20;
const ll oo = 1e9 + 7;

int n, k;
int A[maxn], val[maxn];
set<int> st, stx; node t[4 * maxn];
int val1[maxn][maxlg], val2[maxn][maxlg];
pll up1[maxn][maxlg], up2[maxn][maxlg];
set<pii> stw; int arr[maxn];

bool cmp(int i, int j) {
	return (val[i] > val[j]);
}

void build(int v, int tl, int tr) {
	t[v].lazy = 0;
	if (tr - tl == 1) {
		t[v].min = Mp(A[tl], tl);
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v].min = min(t[2 * v + 1].min, t[2 * v + 2].min); t[v].min.F += t[v].lazy;
}

void add_val(int v, int tl, int tr, int l, int r, ll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	if (l == tl && r == tr) {
		t[v].min.F += x; t[v].lazy += x;
		return ;
	}
	int mid = (tl + tr) / 2;
	add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
	t[v].min = min(t[2 * v + 1].min, t[2 * v + 2].min); t[v].min.F += t[v].lazy;
}

void checkx(int j) {
	stx.erase(j); int d = 0;
	auto it = st.lower_bound(j);
	if (it != st.begin()) {
		it--; d = (j - *it);
	}
	else d = (j - *st.rbegin() + n);
	if (d >= k) stx.insert(j);
}

void addx(int j) {
	st.insert(j); checkx(j);
	if (len(st) == 1) return ;
	auto it = st.upper_bound(j);
	if (it != st.end()) checkx(*it);
	else checkx(*st.begin());
}

bool ok1(int v, int x, int d) {
	ll res = 0;
	for (int j = maxlg - 1; j >= 0; j--) {
		if (val1[v][j] <= x) {
			res += up1[v][j].F;
			v = up1[v][j].S;
			if (res >= d) return 1;
		}
	}
	return (res >= d);
}

int ok2(int v, int x, int d) {
	ll res = 0;
	for (int j = maxlg - 1; j >= 0; j--) {
		if (val2[v][j] <= x) {
			res += up2[v][j].F;
			v = up2[v][j].S;
			if (res >= d) return 1;
		}
	}
	return (res >= d);
}

void delx(int j) {
	st.erase(j); stx.erase(j);
	if (len(st) == 0) return ;
	auto it = st.upper_bound(j);
	if (it != st.end()) checkx(*it);
	else checkx(*st.begin());
}

void init(int Kx, vector<int> Ax) {
	n = len(Ax); k = Kx;
	
	for (int i = 0; i < n; i++) A[i] = Ax[i];
	build(0, 0, n);
	
	int sz = 0;
	while (sz < n) {
		while (t[0].min.F == 0) {
			int j = t[0].min.S;
			add_val(0, 0, n, j, j + 1, oo);
			addx(j);
		}
		int j = *stx.begin(); val[j] = sz++;
		int x1 = min(j, k - 1), x2 = (k - 1) - x1;
		add_val(0, 0, n, j - x1, j, -1);
		add_val(0, 0, n, n - x2, n, -1);
		delx(j);
	}
	
	stw.clear();
	for (int j = 0; j < k; j++) stw.insert(Mp(val[j], j));
	for (int i = 0; i < n; i++) {
		int j = (i + k - 1) % n, r = -1;
		
		auto it = stw.upper_bound(Mp(val[i], oo));
		if (it != stw.end()) r = (*it).S;
		else r = i;
		up1[i][0] = Mp((r - i + n) % n, r);
		val1[i][0] = val[r];
		
		it = stw.upper_bound(Mp(val[j], oo));
		if (it != stw.end()) r = (*it).S;
		else r = j;
		up2[j][0] = Mp((j - r + n) % n, r);
		val2[j][0] = val[r];
		
		stw.erase(Mp(val[i], i));
		r = (i + k) % n;
		stw.insert(Mp(val[r], r));
	}
	
	iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
	for (int i = 0; i < n; i++) {
		int v = arr[i];
		for (int j = 1; j < maxlg; j++) {
			int u = up1[v][j - 1].S;
			up1[v][j] = Mp(up1[v][j - 1].F + up1[u][j - 1].F, up1[u][j - 1].S);
			val1[v][j] = val1[u][j - 1];
			
			u = up2[v][j - 1].S;
			up2[v][j] = Mp(up2[v][j - 1].F + up2[u][j - 1].F, up2[u][j - 1].S);
			val2[v][j] = val2[u][j - 1];
		}
	}
	
	return ;
}

int compare_plants(int x, int y) {
	if (val[x] < val[y]) {
		int d1 = (y - x + n) % n;
		int d2 = (x - y + n) % n;
		if (!ok1(x, val[y], d1) && !ok2(x, val[y], d2)) return 0;
	}
	else {
		int d1 = (x - y + n) % n;
		int d2 = (y - x + n) % n;
		if (!ok1(y, val[x], d1) && !ok2(y, val[x], d2)) return 0;
	}
	
	if (val[x] < val[y]) return 1;
	else return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19544 KB Output is correct
2 Correct 6 ms 19548 KB Output is correct
3 Correct 6 ms 19548 KB Output is correct
4 Correct 6 ms 19548 KB Output is correct
5 Correct 8 ms 19768 KB Output is correct
6 Correct 47 ms 22620 KB Output is correct
7 Correct 95 ms 39700 KB Output is correct
8 Correct 369 ms 186964 KB Output is correct
9 Correct 360 ms 186548 KB Output is correct
10 Correct 382 ms 186448 KB Output is correct
11 Correct 421 ms 186960 KB Output is correct
12 Correct 471 ms 186960 KB Output is correct
13 Correct 554 ms 191400 KB Output is correct
14 Correct 495 ms 181940 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20828 KB Output is correct
2 Correct 6 ms 19548 KB Output is correct
3 Correct 6 ms 20828 KB Output is correct
4 Correct 6 ms 19548 KB Output is correct
5 Correct 6 ms 21084 KB Output is correct
6 Correct 9 ms 20572 KB Output is correct
7 Correct 51 ms 26764 KB Output is correct
8 Correct 7 ms 19800 KB Output is correct
9 Correct 9 ms 20572 KB Output is correct
10 Correct 51 ms 26692 KB Output is correct
11 Correct 67 ms 27732 KB Output is correct
12 Correct 70 ms 26708 KB Output is correct
13 Correct 51 ms 26708 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20828 KB Output is correct
2 Correct 6 ms 19548 KB Output is correct
3 Correct 6 ms 20828 KB Output is correct
4 Correct 6 ms 19548 KB Output is correct
5 Correct 6 ms 21084 KB Output is correct
6 Correct 9 ms 20572 KB Output is correct
7 Correct 51 ms 26764 KB Output is correct
8 Correct 7 ms 19800 KB Output is correct
9 Correct 9 ms 20572 KB Output is correct
10 Correct 51 ms 26692 KB Output is correct
11 Correct 67 ms 27732 KB Output is correct
12 Correct 70 ms 26708 KB Output is correct
13 Correct 51 ms 26708 KB Output is correct
14 Correct 86 ms 40272 KB Output is correct
15 Correct 674 ms 187764 KB Output is correct
16 Correct 88 ms 39008 KB Output is correct
17 Correct 655 ms 187736 KB Output is correct
18 Correct 647 ms 186748 KB Output is correct
19 Correct 511 ms 186704 KB Output is correct
20 Correct 688 ms 191568 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19544 KB Output is correct
2 Correct 6 ms 19804 KB Output is correct
3 Correct 61 ms 24168 KB Output is correct
4 Correct 541 ms 185172 KB Output is correct
5 Correct 509 ms 182608 KB Output is correct
6 Correct 472 ms 182096 KB Output is correct
7 Correct 567 ms 182356 KB Output is correct
8 Correct 631 ms 186212 KB Output is correct
9 Correct 418 ms 184148 KB Output is correct
10 Correct 472 ms 182664 KB Output is correct
11 Correct 558 ms 191312 KB Output is correct
12 Correct 513 ms 181840 KB Output is correct
13 Correct 611 ms 188524 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19548 KB Output is correct
2 Correct 6 ms 20832 KB Output is correct
3 Correct 6 ms 19548 KB Output is correct
4 Correct 6 ms 19548 KB Output is correct
5 Correct 7 ms 20828 KB Output is correct
6 Correct 10 ms 21340 KB Output is correct
7 Correct 18 ms 20548 KB Output is correct
8 Correct 15 ms 20552 KB Output is correct
9 Correct 17 ms 21784 KB Output is correct
10 Correct 14 ms 20568 KB Output is correct
11 Correct 17 ms 20412 KB Output is correct
12 Correct 16 ms 20572 KB Output is correct
13 Correct 15 ms 20568 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19544 KB Output is correct
2 Correct 7 ms 19544 KB Output is correct
3 Correct 7 ms 19544 KB Output is correct
4 Correct 7 ms 19548 KB Output is correct
5 Correct 8 ms 21596 KB Output is correct
6 Correct 509 ms 182184 KB Output is correct
7 Correct 530 ms 181908 KB Output is correct
8 Correct 522 ms 182420 KB Output is correct
9 Correct 622 ms 186196 KB Output is correct
10 Correct 447 ms 184148 KB Output is correct
11 Correct 491 ms 185932 KB Output is correct
12 Correct 416 ms 184932 KB Output is correct
13 Correct 471 ms 182612 KB Output is correct
14 Correct 448 ms 182100 KB Output is correct
15 Correct 542 ms 182356 KB Output is correct
16 Correct 433 ms 183468 KB Output is correct
17 Correct 461 ms 182100 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19544 KB Output is correct
2 Correct 6 ms 19548 KB Output is correct
3 Correct 6 ms 19548 KB Output is correct
4 Correct 6 ms 19548 KB Output is correct
5 Correct 8 ms 19768 KB Output is correct
6 Correct 47 ms 22620 KB Output is correct
7 Correct 95 ms 39700 KB Output is correct
8 Correct 369 ms 186964 KB Output is correct
9 Correct 360 ms 186548 KB Output is correct
10 Correct 382 ms 186448 KB Output is correct
11 Correct 421 ms 186960 KB Output is correct
12 Correct 471 ms 186960 KB Output is correct
13 Correct 554 ms 191400 KB Output is correct
14 Correct 495 ms 181940 KB Output is correct
15 Correct 7 ms 20828 KB Output is correct
16 Correct 6 ms 19548 KB Output is correct
17 Correct 6 ms 20828 KB Output is correct
18 Correct 6 ms 19548 KB Output is correct
19 Correct 6 ms 21084 KB Output is correct
20 Correct 9 ms 20572 KB Output is correct
21 Correct 51 ms 26764 KB Output is correct
22 Correct 7 ms 19800 KB Output is correct
23 Correct 9 ms 20572 KB Output is correct
24 Correct 51 ms 26692 KB Output is correct
25 Correct 67 ms 27732 KB Output is correct
26 Correct 70 ms 26708 KB Output is correct
27 Correct 51 ms 26708 KB Output is correct
28 Correct 86 ms 40272 KB Output is correct
29 Correct 674 ms 187764 KB Output is correct
30 Correct 88 ms 39008 KB Output is correct
31 Correct 655 ms 187736 KB Output is correct
32 Correct 647 ms 186748 KB Output is correct
33 Correct 511 ms 186704 KB Output is correct
34 Correct 688 ms 191568 KB Output is correct
35 Correct 6 ms 19544 KB Output is correct
36 Correct 6 ms 19804 KB Output is correct
37 Correct 61 ms 24168 KB Output is correct
38 Correct 541 ms 185172 KB Output is correct
39 Correct 509 ms 182608 KB Output is correct
40 Correct 472 ms 182096 KB Output is correct
41 Correct 567 ms 182356 KB Output is correct
42 Correct 631 ms 186212 KB Output is correct
43 Correct 418 ms 184148 KB Output is correct
44 Correct 472 ms 182664 KB Output is correct
45 Correct 558 ms 191312 KB Output is correct
46 Correct 513 ms 181840 KB Output is correct
47 Correct 611 ms 188524 KB Output is correct
48 Correct 6 ms 19548 KB Output is correct
49 Correct 6 ms 20832 KB Output is correct
50 Correct 6 ms 19548 KB Output is correct
51 Correct 6 ms 19548 KB Output is correct
52 Correct 7 ms 20828 KB Output is correct
53 Correct 10 ms 21340 KB Output is correct
54 Correct 18 ms 20548 KB Output is correct
55 Correct 15 ms 20552 KB Output is correct
56 Correct 17 ms 21784 KB Output is correct
57 Correct 14 ms 20568 KB Output is correct
58 Correct 17 ms 20412 KB Output is correct
59 Correct 16 ms 20572 KB Output is correct
60 Correct 15 ms 20568 KB Output is correct
61 Correct 68 ms 24144 KB Output is correct
62 Correct 106 ms 38608 KB Output is correct
63 Correct 427 ms 183640 KB Output is correct
64 Correct 485 ms 182100 KB Output is correct
65 Correct 556 ms 181844 KB Output is correct
66 Correct 566 ms 182424 KB Output is correct
67 Correct 608 ms 186192 KB Output is correct
68 Correct 458 ms 184420 KB Output is correct
69 Correct 572 ms 185944 KB Output is correct
70 Correct 497 ms 185168 KB Output is correct
71 Correct 515 ms 182868 KB Output is correct
72 Correct 528 ms 181980 KB Output is correct
73 Correct 539 ms 182356 KB Output is correct
74 Correct 424 ms 182868 KB Output is correct
75 Correct 426 ms 182252 KB Output is correct