oj.uz

Submission #1039809

# Submission time Handle Problem Language Result Execution time Memory
1039809 2024-07-31T09:37:32 Z AmirAli_H1 Comparing Plants (IOI20_plants) C++17
30 / 100
 796 ms 131808 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];
pii 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());
}

int get_val1(int v, ll x) {
	int 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;
		}
	}
	return res;
}

int get_val2(int v, ll x) {
	int 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;
		}
	}
	return res;
}

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 (get_val1(x, val[y]) < d1 && get_val2(x, val[y]) < d2) return 0;
	}
	else {
		int d1 = (x - y + n) % n;
		int d2 = (y - x + n) % n;
		if (get_val1(y, val[x]) < d1 && get_val2(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 9 ms 19292 KB Output is correct
2 Correct 6 ms 19404 KB Output is correct
3 Correct 4 ms 25436 KB Output is correct
4 Correct 3 ms 19288 KB Output is correct
5 Correct 4 ms 19408 KB Output is correct
6 Correct 49 ms 27220 KB Output is correct
7 Correct 84 ms 35180 KB Output is correct
8 Correct 355 ms 127316 KB Output is correct
9 Correct 334 ms 126800 KB Output is correct
10 Correct 368 ms 126856 KB Output is correct
11 Correct 386 ms 127304 KB Output is correct
12 Correct 409 ms 127204 KB Output is correct
13 Correct 437 ms 131808 KB Output is correct
14 Correct 453 ms 122352 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19292 KB Output is correct
2 Correct 5 ms 19292 KB Output is correct
3 Correct 5 ms 19292 KB Output is correct
4 Correct 5 ms 19288 KB Output is correct
5 Correct 5 ms 19292 KB Output is correct
6 Correct 7 ms 20060 KB Output is correct
7 Correct 70 ms 26628 KB Output is correct
8 Correct 6 ms 19544 KB Output is correct
9 Correct 7 ms 20060 KB Output is correct
10 Correct 88 ms 26552 KB Output is correct
11 Correct 69 ms 26496 KB Output is correct
12 Correct 69 ms 26704 KB Output is correct
13 Correct 68 ms 26704 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19292 KB Output is correct
2 Correct 5 ms 19292 KB Output is correct
3 Correct 5 ms 19292 KB Output is correct
4 Correct 5 ms 19288 KB Output is correct
5 Correct 5 ms 19292 KB Output is correct
6 Correct 7 ms 20060 KB Output is correct
7 Correct 70 ms 26628 KB Output is correct
8 Correct 6 ms 19544 KB Output is correct
9 Correct 7 ms 20060 KB Output is correct
10 Correct 88 ms 26552 KB Output is correct
11 Correct 69 ms 26496 KB Output is correct
12 Correct 69 ms 26704 KB Output is correct
13 Correct 68 ms 26704 KB Output is correct
14 Correct 99 ms 36436 KB Output is correct
15 Incorrect 796 ms 128844 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21340 KB Output is correct
2 Correct 3 ms 23384 KB Output is correct
3 Correct 57 ms 28244 KB Output is correct
4 Correct 449 ms 125404 KB Output is correct
5 Correct 433 ms 123008 KB Output is correct
6 Correct 512 ms 122704 KB Output is correct
7 Correct 492 ms 123328 KB Output is correct
8 Incorrect 672 ms 127104 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 3 ms 23640 KB Output is correct
2 Correct 3 ms 23388 KB Output is correct
3 Correct 2 ms 21340 KB Output is correct
4 Correct 3 ms 21340 KB Output is correct
5 Correct 3 ms 23384 KB Output is correct
6 Correct 4 ms 21596 KB Output is correct
7 Correct 13 ms 22364 KB Output is correct
8 Correct 12 ms 24412 KB Output is correct
9 Correct 13 ms 24348 KB Output is correct
10 Correct 11 ms 24412 KB Output is correct
11 Correct 13 ms 22360 KB Output is correct
12 Correct 14 ms 24532 KB Output is correct
13 Correct 13 ms 22364 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23388 KB Output is correct
2 Correct 3 ms 21340 KB Output is correct
3 Correct 2 ms 21340 KB Output is correct
4 Correct 3 ms 23516 KB Output is correct
5 Correct 5 ms 23644 KB Output is correct
6 Correct 423 ms 121608 KB Output is correct
7 Correct 463 ms 121684 KB Output is correct
8 Correct 509 ms 122464 KB Output is correct
9 Incorrect 669 ms 126240 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19292 KB Output is correct
2 Correct 6 ms 19404 KB Output is correct
3 Correct 4 ms 25436 KB Output is correct
4 Correct 3 ms 19288 KB Output is correct
5 Correct 4 ms 19408 KB Output is correct
6 Correct 49 ms 27220 KB Output is correct
7 Correct 84 ms 35180 KB Output is correct
8 Correct 355 ms 127316 KB Output is correct
9 Correct 334 ms 126800 KB Output is correct
10 Correct 368 ms 126856 KB Output is correct
11 Correct 386 ms 127304 KB Output is correct
12 Correct 409 ms 127204 KB Output is correct
13 Correct 437 ms 131808 KB Output is correct
14 Correct 453 ms 122352 KB Output is correct
15 Correct 7 ms 19292 KB Output is correct
16 Correct 5 ms 19292 KB Output is correct
17 Correct 5 ms 19292 KB Output is correct
18 Correct 5 ms 19288 KB Output is correct
19 Correct 5 ms 19292 KB Output is correct
20 Correct 7 ms 20060 KB Output is correct
21 Correct 70 ms 26628 KB Output is correct
22 Correct 6 ms 19544 KB Output is correct
23 Correct 7 ms 20060 KB Output is correct
24 Correct 88 ms 26552 KB Output is correct
25 Correct 69 ms 26496 KB Output is correct
26 Correct 69 ms 26704 KB Output is correct
27 Correct 68 ms 26704 KB Output is correct
28 Correct 99 ms 36436 KB Output is correct
29 Incorrect 796 ms 128844 KB Output isn't correct
30 Halted 0 ms 0 KB -