oj.uz

Submission #821677

# Submission time Handle Problem Language Result Execution time Memory
821677 2023-08-11T12:59:37 Z Abrar_Al_Samit Comparing Plants (IOI20_plants) C++17
27 / 100
 268 ms 19824 KB 
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

const int nax = 2e5 + 2;
const int inf = 2e9;


int val[nax], n, k;
struct plant {
	int id;

	plant(int _id = 0) {
		id = _id;
	}

	bool operator<(plant b) const {
		if(id + k - 1 < n) {
			return b.id > id && b.id <= id + k - 1;
		} else {
			if(b.id < id) return (id + k - 1) % n >= b.id;
			else return b.id > id;
		}
	}
};

int stree[nax * 4], at[nax * 4], lztree[nax * 4], del;

void propagate(int v) {
	stree[v << 1] += lztree[v];
	stree[v << 1 | 1] += lztree[v];
	lztree[v << 1] += lztree[v];
	lztree[v << 1 | 1] += lztree[v];
	lztree[v] = 0;
}
void update(int L, int R, int l = 0, int r = n-1, int v = 1) {
	if(l >= L && r <= R) {
		lztree[v] += del;
		stree[v] += del;
		return;
	}
	if(l > R || r < L) return;
	propagate(v);

	int mid = (l + r) >> 1;
	update(L, R, l, mid, v << 1);
	update(L, R, mid+1, r, v << 1 | 1);

	stree[v] = min(stree[v << 1], stree[v << 1 | 1]);
	at[v] = (stree[v << 1] < stree[v << 1 | 1]) ? at[v << 1] : at[v << 1 | 1];
}
void upd(int L, int R) {
	if(L < 0) {
		update(0, R);
		L += n;
		update(L, n-1);
	} else {
		update(L, R);
	}
}
vector<int>R;
void build(int l = 0, int r = n-1, int v = 1) {
	if(l == r) {
		stree[v] = R[l];
		at[v] = l;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, v << 1);
	build(mid+1, r, v << 1 | 1);
	stree[v] = min(stree[v << 1], stree[v << 1 | 1]);
	at[v] = (stree[v << 1] < stree[v << 1 | 1]) ? at[v << 1] : at[v << 1 | 1];	
}

void init(int K, vector<int> r) {
	k = K;
	n = r.size();
	R = r;

	build();

	set<plant>cand;
	for(int tg=n; tg>=1; --tg) {
		while(stree[1]==0) {
			int mat = at[1];
			cand.insert(plant(mat));

			del = inf;
			upd(mat, mat);
		}

		plant mx = *cand.begin();
		cand.erase(mx);

		val[mx.id] = tg;
		del = -1;
		upd(mx.id - k + 1, mx.id);
	}
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 212 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 412 KB Output is correct
7 Correct 44 ms 5308 KB Output is correct
8 Correct 2 ms 416 KB Output is correct
9 Correct 2 ms 412 KB Output is correct
10 Correct 42 ms 5308 KB Output is correct
11 Correct 41 ms 5228 KB Output is correct
12 Correct 41 ms 5428 KB Output is correct
13 Correct 42 ms 5232 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 412 KB Output is correct
7 Correct 44 ms 5308 KB Output is correct
8 Correct 2 ms 416 KB Output is correct
9 Correct 2 ms 412 KB Output is correct
10 Correct 42 ms 5308 KB Output is correct
11 Correct 41 ms 5228 KB Output is correct
12 Correct 41 ms 5428 KB Output is correct
13 Correct 42 ms 5232 KB Output is correct
14 Correct 57 ms 6388 KB Output is correct
15 Correct 268 ms 15668 KB Output is correct
16 Correct 57 ms 6380 KB Output is correct
17 Correct 255 ms 15736 KB Output is correct
18 Correct 231 ms 19824 KB Output is correct
19 Correct 171 ms 15668 KB Output is correct
20 Correct 263 ms 15692 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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