oj.uz

Submission #1039790

# Submission time Handle Problem Language Result Execution time Memory
1039790 2024-07-31T09:00:06 Z AmirAli_H1 Comparing Plants (IOI20_plants) C++17
44 / 100
 259 ms 36944 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 ll oo = 1e9 + 7;

int n, k;
int A[maxn], val[maxn];
set<int> st, stx;
node t[4 * maxn];

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());
}

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);
	}
	
	return;
}

int compare_plants(int x, int y) {
	if (val[x] < val[y]) return 1;
	else return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 19036 KB Output is correct
3 Correct 3 ms 19292 KB Output is correct
4 Incorrect 2 ms 19036 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19236 KB Output is correct
2 Correct 2 ms 19076 KB Output is correct
3 Correct 2 ms 19036 KB Output is correct
4 Correct 2 ms 19036 KB Output is correct
5 Correct 2 ms 19036 KB Output is correct
6 Correct 4 ms 19292 KB Output is correct
7 Correct 38 ms 23912 KB Output is correct
8 Correct 3 ms 19292 KB Output is correct
9 Correct 4 ms 19292 KB Output is correct
10 Correct 37 ms 24020 KB Output is correct
11 Correct 36 ms 24016 KB Output is correct
12 Correct 36 ms 24144 KB Output is correct
13 Correct 45 ms 24152 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19236 KB Output is correct
2 Correct 2 ms 19076 KB Output is correct
3 Correct 2 ms 19036 KB Output is correct
4 Correct 2 ms 19036 KB Output is correct
5 Correct 2 ms 19036 KB Output is correct
6 Correct 4 ms 19292 KB Output is correct
7 Correct 38 ms 23912 KB Output is correct
8 Correct 3 ms 19292 KB Output is correct
9 Correct 4 ms 19292 KB Output is correct
10 Correct 37 ms 24020 KB Output is correct
11 Correct 36 ms 24016 KB Output is correct
12 Correct 36 ms 24144 KB Output is correct
13 Correct 45 ms 24152 KB Output is correct
14 Correct 52 ms 24404 KB Output is correct
15 Correct 246 ms 28244 KB Output is correct
16 Correct 52 ms 24472 KB Output is correct
17 Correct 241 ms 28240 KB Output is correct
18 Correct 232 ms 32688 KB Output is correct
19 Correct 152 ms 28240 KB Output is correct
20 Correct 240 ms 28248 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 19036 KB Output is correct
3 Correct 36 ms 23632 KB Output is correct
4 Correct 178 ms 30548 KB Output is correct
5 Correct 219 ms 28244 KB Output is correct
6 Correct 229 ms 27876 KB Output is correct
7 Correct 259 ms 27984 KB Output is correct
8 Correct 239 ms 28240 KB Output is correct
9 Correct 202 ms 29996 KB Output is correct
10 Correct 216 ms 28256 KB Output is correct
11 Correct 212 ms 36944 KB Output is correct
12 Correct 136 ms 27732 KB Output is correct
13 Correct 234 ms 34384 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19032 KB Output is correct
3 Incorrect 2 ms 19240 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 19036 KB Output is correct
3 Incorrect 2 ms 19036 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19036 KB Output is correct
2 Correct 2 ms 19036 KB Output is correct
3 Correct 3 ms 19292 KB Output is correct
4 Incorrect 2 ms 19036 KB Output isn't correct
5 Halted 0 ms 0 KB -