oj.uz

Submission #837339

# Submission time Handle Problem Language Result Execution time Memory
837339 2023-08-25T09:41:55 Z pavement Comparing Plants (IOI20_plants) C++17
27 / 100
 4000 ms 32452 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair

using ii = pair<int, int>;

int n;
vector<int> r, h;

struct node {
	node *left, *right;
	int S, E, pv;
	ii val;
	node(int _s, int _e) : S(_s), E(_e), pv(0) {
		if (S == E) {
			val = mp(r[S], S);
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M);
		right = new node(M + 1, E);
		val = min(left->val, right->val);
	}
	void prop() {
		if (S == E || !pv) {
			return;
		}
		left->val.first += pv;
		left->pv += pv;
		right->val.first += pv;
		right->pv += pv;
		pv = 0;
	}
	void upd(int l, int r, int v) {
		if (l > E || r < S) {
			return;
		}
		if (l <= S && E <= r) {
			val.first += v;
			pv += v;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		val = min(left->val, right->val);
	}
} *root;

void init(int k, vector<int> r) {
	n = (int)r.size();
	::r = r;
	h.resize(n);
	root = new node(0, n - 1);
	set<int> zeroes;
	for (int i = n - 1; i >= 0; i--) {
		while (root->val.first == 0) {
			int cur_pos = root->val.second;
			zeroes.insert(cur_pos);
			root->upd(cur_pos, cur_pos, (int)1e9);
		}
		assert(!zeroes.empty());
		int prv = *zeroes.rbegin(), pos = -1;
		for (int j : zeroes) {
			int dist = j - prv;
			if (dist < 0) {
				dist += n;
			}
			if (j == prv || dist >= k) {
				pos = j;
				zeroes.erase(j);
				break;
			}
			prv = j;
		}
		assert(pos != -1);
		h[pos] = i;
		if (pos - k + 1 < 0) {
			root->upd(pos - k + 1 + n, n - 1, -1);
			root->upd(0, pos - 1, -1);
		} else {
			root->upd(pos - k + 1, pos - 1, -1);
		}
	}
}

int compare_plants(int x, int y) {
	return (h[x] < h[y] ? -1 : 1);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 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 1 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 45 ms 5480 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 42 ms 5468 KB Output is correct
11 Correct 41 ms 5580 KB Output is correct
12 Correct 41 ms 5604 KB Output is correct
13 Correct 42 ms 5476 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 45 ms 5480 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 42 ms 5468 KB Output is correct
11 Correct 41 ms 5580 KB Output is correct
12 Correct 41 ms 5604 KB Output is correct
13 Correct 42 ms 5476 KB Output is correct
14 Correct 58 ms 7508 KB Output is correct
15 Correct 372 ms 28280 KB Output is correct
16 Correct 58 ms 7440 KB Output is correct
17 Correct 339 ms 28280 KB Output is correct
18 Correct 190 ms 32452 KB Output is correct
19 Correct 151 ms 28240 KB Output is correct
20 Correct 279 ms 28248 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 42 ms 5080 KB Output is correct
4 Execution timed out 4059 ms 30604 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 232 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 1 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 1 ms 212 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 -