oj.uz

Submission #1039827

# Submission time Handle Problem Language Result Execution time Memory
1039827 2024-07-31T09:58:14 Z AmirAli_H1 Comparing Plants (IOI20_plants) C++17
30 / 100
 610 ms 128592 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());
}

bool ok1(int v, int x, int d) {
	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;
			if (res >= d) return 1;
		}
	}
	return (res >= d);
}

int ok2(int v, int x, int d) {
	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;
			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 19292 KB Output is correct
3 Correct 6 ms 19292 KB Output is correct
4 Correct 7 ms 19288 KB Output is correct
5 Correct 6 ms 19292 KB Output is correct
6 Correct 47 ms 22232 KB Output is correct
7 Correct 86 ms 31980 KB Output is correct
8 Correct 330 ms 124388 KB Output is correct
9 Correct 324 ms 123736 KB Output is correct
10 Correct 332 ms 123988 KB Output is correct
11 Correct 354 ms 124756 KB Output is correct
12 Correct 390 ms 124152 KB Output is correct
13 Correct 462 ms 128592 KB Output is correct
14 Correct 391 ms 119636 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19288 KB Output is correct
2 Correct 6 ms 19292 KB Output is correct
3 Correct 5 ms 19312 KB Output is correct
4 Correct 6 ms 19292 KB Output is correct
5 Correct 6 ms 19292 KB Output is correct
6 Correct 8 ms 19804 KB Output is correct
7 Correct 51 ms 24656 KB Output is correct
8 Correct 8 ms 19544 KB Output is correct
9 Correct 8 ms 19804 KB Output is correct
10 Correct 51 ms 24852 KB Output is correct
11 Correct 65 ms 24660 KB Output is correct
12 Correct 70 ms 24844 KB Output is correct
13 Correct 50 ms 24912 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19288 KB Output is correct
2 Correct 6 ms 19292 KB Output is correct
3 Correct 5 ms 19312 KB Output is correct
4 Correct 6 ms 19292 KB Output is correct
5 Correct 6 ms 19292 KB Output is correct
6 Correct 8 ms 19804 KB Output is correct
7 Correct 51 ms 24656 KB Output is correct
8 Correct 8 ms 19544 KB Output is correct
9 Correct 8 ms 19804 KB Output is correct
10 Correct 51 ms 24852 KB Output is correct
11 Correct 65 ms 24660 KB Output is correct
12 Correct 70 ms 24844 KB Output is correct
13 Correct 50 ms 24912 KB Output is correct
14 Correct 83 ms 32336 KB Output is correct
15 Incorrect 610 ms 125008 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19288 KB Output is correct
2 Correct 6 ms 19424 KB Output is correct
3 Correct 60 ms 23052 KB Output is correct
4 Correct 429 ms 122452 KB Output is correct
5 Correct 412 ms 119888 KB Output is correct
6 Correct 515 ms 119636 KB Output is correct
7 Correct 487 ms 119828 KB Output is correct
8 Incorrect 577 ms 123472 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 7 ms 19288 KB Output is correct
2 Correct 7 ms 19292 KB Output is correct
3 Correct 6 ms 19292 KB Output is correct
4 Correct 7 ms 19292 KB Output is correct
5 Correct 6 ms 19292 KB Output is correct
6 Correct 8 ms 19376 KB Output is correct
7 Correct 19 ms 20060 KB Output is correct
8 Correct 19 ms 20056 KB Output is correct
9 Correct 16 ms 20056 KB Output is correct
10 Correct 15 ms 20204 KB Output is correct
11 Correct 18 ms 20196 KB Output is correct
12 Correct 16 ms 20060 KB Output is correct
13 Correct 15 ms 20060 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19292 KB Output is correct
2 Correct 6 ms 19292 KB Output is correct
3 Correct 6 ms 19292 KB Output is correct
4 Correct 6 ms 19400 KB Output is correct
5 Correct 7 ms 19804 KB Output is correct
6 Correct 463 ms 119320 KB Output is correct
7 Correct 464 ms 119376 KB Output is correct
8 Correct 476 ms 119812 KB Output is correct
9 Incorrect 600 ms 123476 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19544 KB Output is correct
2 Correct 6 ms 19292 KB Output is correct
3 Correct 6 ms 19292 KB Output is correct
4 Correct 7 ms 19288 KB Output is correct
5 Correct 6 ms 19292 KB Output is correct
6 Correct 47 ms 22232 KB Output is correct
7 Correct 86 ms 31980 KB Output is correct
8 Correct 330 ms 124388 KB Output is correct
9 Correct 324 ms 123736 KB Output is correct
10 Correct 332 ms 123988 KB Output is correct
11 Correct 354 ms 124756 KB Output is correct
12 Correct 390 ms 124152 KB Output is correct
13 Correct 462 ms 128592 KB Output is correct
14 Correct 391 ms 119636 KB Output is correct
15 Correct 6 ms 19288 KB Output is correct
16 Correct 6 ms 19292 KB Output is correct
17 Correct 5 ms 19312 KB Output is correct
18 Correct 6 ms 19292 KB Output is correct
19 Correct 6 ms 19292 KB Output is correct
20 Correct 8 ms 19804 KB Output is correct
21 Correct 51 ms 24656 KB Output is correct
22 Correct 8 ms 19544 KB Output is correct
23 Correct 8 ms 19804 KB Output is correct
24 Correct 51 ms 24852 KB Output is correct
25 Correct 65 ms 24660 KB Output is correct
26 Correct 70 ms 24844 KB Output is correct
27 Correct 50 ms 24912 KB Output is correct
28 Correct 83 ms 32336 KB Output is correct
29 Incorrect 610 ms 125008 KB Output isn't correct
30 Halted 0 ms 0 KB -