oj.uz

Submission #770861

# Submission time Handle Problem Language Result Execution time Memory
770861 2023-07-02T05:06:47 Z SanguineChameleon Comparing Plants (IOI20_plants) C++17
14 / 100
 58 ms 14320 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 20;
const int inf = 1e9 + 20;
int a[maxn];
pair<int, int> tree[maxn];
int lazy[maxn];
int pos[maxn];
int n, k;

bool cmp(pair<int, int> p1, pair<int, int> p2) {
	if (p1.first != p2.first) {
		return p1.first < p2.first;
	}
	else if (p1.second < p2.second && p2.second - p1.second + 1 <= k) {
		return true;
	}
	else if (p1.second > p2.second && n - (p1.second - p2.second - 1) <= k) {
		return true;
	}
	else {
		return false;
	}
}

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tree[id] = make_pair(a[lt], lt);
		return;
	}
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt);
	build(id * 2 + 1, mt + 1, rt);
	tree[id] = min(tree[id * 2], tree[id * 2 + 1], cmp);
}

void update(int id, int lt, int rt, int ql, int qr, int add) {
	if (lt == ql && rt == qr) {
		tree[id].first += add;
		lazy[id] += add;
		return;
	}
	tree[id * 2].first += lazy[id];
	lazy[id * 2] += lazy[id];
	tree[id * 2 + 1].first += lazy[id];
	lazy[id * 2 + 1] += lazy[id];
	lazy[id] = 0;
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		update(id * 2, lt, mt, ql, qr, add);
	}
	else if (ql >= mt + 1) {
		update(id * 2 + 1, mt + 1, rt, ql, qr, add);
	}
	else {
		update(id * 2, lt, mt, ql, mt, add);
		update(id * 2 + 1, mt + 1, rt, mt + 1, qr, add);
	}
	tree[id] = min(tree[id * 2], tree[id * 2 + 1], cmp);
}

void init(int _k, vector<int> _a) {
	n = _a.size();
	k = _k;
	for (int i = 0; i < n; i++) {
		a[i] = k - 1 - _a[i];
	}
	build(1, 0, n - 1);
	for (int i = 0; i < n; i++) {
		int rt = tree[1].second;
		int lt = (rt + n - (k - 1)) % n;
		pos[rt] = i;
		update(1, 0, n - 1, rt, rt, inf);
		if (lt <= rt) {
			update(1, 0, n - 1, lt, rt, -1);
		}
		else {
			update(1, 0, n - 1, lt, n - 1, -1);
			update(1, 0, n - 1, 0, rt, -1);
		}
	}
	return;
}

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

Subtask #1
0 / 5.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 0 ms 212 KB Output isn't correct
4 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 1 ms 308 KB Output is correct
3 Correct 0 ms 308 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 440 KB Output is correct
7 Correct 43 ms 5308 KB Output is correct
8 Correct 1 ms 396 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 43 ms 5236 KB Output is correct
11 Correct 42 ms 5164 KB Output is correct
12 Correct 42 ms 5360 KB Output is correct
13 Correct 43 ms 5232 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 308 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 440 KB Output is correct
7 Correct 43 ms 5308 KB Output is correct
8 Correct 1 ms 396 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 43 ms 5236 KB Output is correct
11 Correct 42 ms 5164 KB Output is correct
12 Correct 42 ms 5360 KB Output is correct
13 Correct 43 ms 5232 KB Output is correct
14 Correct 58 ms 6492 KB Output is correct
15 Runtime error 50 ms 14320 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 41 ms 4960 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 0 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 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 1 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 -