oj.uz

Submission #1050488

# Submission time Handle Problem Language Result Execution time Memory
1050488 2024-08-09T10:11:27 Z dozer Comparing Plants (IOI20_plants) C++14
44 / 100
 438 ms 38228 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sp " "
#define endl "\n"
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 2000005

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;

int val[MAXN], lazy[4 * MAXN];

pii tree[4 * MAXN];

void push(int node, int l, int r){
	tree[node].st += lazy[node];
	if (l != r){
		lazy[LL] += lazy[node];
		lazy[RR] += lazy[node];
	}
	lazy[node] = 0;
}

void update(int node, int l, int r, int sl, int val){
	push(node, l, r);
	if (l > sl || r < sl) return;
	if (l == r){
		tree[node].st = val;
		return;
	}

	int mid = (l + r) / 2;
	update(LL, l, mid, sl, val);
	update(RR, mid + 1, r, sl, val);
	tree[node] = min(tree[LL], tree[RR]);
}

void update(int node, int l, int r, int sl, int sr, int val){
	push(node, l, r);
	if (l > sr || r < sl) return;
	if (l >= sl && r <= sr){
		lazy[node] += val;
		push(node, l, r);
		return;
	}

	int mid = (l + r) / 2;
	update(LL, l, mid, sl, sr, val);
	update(RR, mid + 1, r, sl, sr, val);
	tree[node] = min(tree[LL], tree[RR]);
}

void build(int node, int l, int r){
	tree[node] = {0, l};
	if (l == r) return;
	int mid = (l + r) / 2;
	build(LL, l, mid);
	build(RR, mid + 1, r);
}

pii query(int node, int l, int r, int sl, int sr){
	push(node, l, r);
	if (l > sr || r < sl) return {modulo, modulo};
	if (l >= sl && r <= sr) return tree[node];
	int mid = (l + r) / 2;
	return min(query(LL, l, mid, sl, sr), query(RR, mid + 1, r, sl, sr));
}


void init(int k, vector<int> r) {
	int n = r.size();
	vector<int> done(n, 0);
	set<int> todo;
	set<pii> dist;

	build(1, 0, n - 1);
	for (int i = 0; i < n; i++){
		update(1, 0, n - 1, i, r[i]);
	}
	

	auto add = [&](int x){
		if (todo.empty()){
			todo.insert(x);
			return;
		}
		if (todo.size() == 1){
			int tmp = *todo.begin();
			dist.insert({(x - tmp + n) % n, x});
			dist.insert({(tmp - x + n) % n, tmp});
			todo.insert(x);
			return;
		}

		auto it = todo.lower_bound(x);
		auto it2 = todo.lower_bound(x);
		if (it == todo.begin()){
			it = todo.lower_bound(*todo.rbegin());
		}
		else{
			it--;
		}
		if (it2 == todo.end()) it2 = todo.begin();
		int l = *it, r = *it2;
		dist.erase({(r - l + n) % n, r});
		dist.insert({(r - x + n) % n, r});
		dist.insert({(x - l + n) % n, x});
		todo.insert(x);
	};

	auto del = [&](int x){
		todo.erase(x);
		if (todo.empty()){
			return;
		}
		if (todo.size() == 1){
			int tmp = *todo.begin();
			dist.erase({(x - tmp + n) % n, x});
			dist.erase({(tmp - x + n) % n, tmp});
			return;
		}

		auto it = todo.lower_bound(x);
		auto it2 = todo.lower_bound(x);
		if (it == todo.begin()){
			it = todo.lower_bound(*todo.rbegin());
		}
		else{
			it--;
		}
		if (it2 == todo.end()) it2 = todo.begin();
		int l = *it, r = *it2;
		dist.insert({(r - l + n) % n, r});
		dist.erase({(r - x + n) % n, r});
		dist.erase({(x - l + n) % n, x});
	};


	auto recompute = [&](){
		int start = 0;
		while(start < n){
			pii tmp = query(1, 0, n - 1, start, n - 1);
			if (tmp.st <= 0){
				add(tmp.nd);
				update(1, 0, n - 1, tmp.nd, modulo);
				start = tmp.nd + 1;
			}
			else{
				break;
			}
		}
	};

	int cntr = 0;
	recompute();

	while(!todo.empty()){
		pii tmp = {0, *todo.begin()};
		if (!dist.empty()) tmp = *dist.rbegin();
		int start = tmp.nd;
		val[start] = cntr++;
		del(start);
		if (start >= k - 1){
			update(1, 0, n - 1, start - (k - 1), start - 1, -1);
		}
		else{
			update(1, 0, n - 1, 0, start - 1, -1);
			int to = (start - (k - 1) + n) % n;
			update(1, 0, n - 1, to, n - 1, -1);
		}

		recompute();
	}
	
}

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

/*
static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
	fileio();
	assert(scanf("%d%d%d", &n, &k, &q) == 3);
	r.resize(n);
	answer.resize(q);
	for (int i = 0; i < n; i++) {
		int value;
		assert(scanf("%d", &value) == 1);
		r[i] = value;
	}
	x.resize(q);
	y.resize(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	init(k, r);
	for (int i = 0; i < q; i++) {
		answer[i] = compare_plants(x[i], y[i]);
	}

	for (int i = 0; i < q; i++) {
		printf("%d\n", answer[i]);
	}

	fclose(stdout);

	return 0;
}*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 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 2392 KB Output is correct
2 Correct 0 ms 2492 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 2 ms 2504 KB Output is correct
7 Correct 32 ms 5352 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 32 ms 6644 KB Output is correct
11 Correct 34 ms 6996 KB Output is correct
12 Correct 30 ms 6740 KB Output is correct
13 Correct 35 ms 6624 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2492 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 2 ms 2504 KB Output is correct
7 Correct 32 ms 5352 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 32 ms 6644 KB Output is correct
11 Correct 34 ms 6996 KB Output is correct
12 Correct 30 ms 6740 KB Output is correct
13 Correct 35 ms 6624 KB Output is correct
14 Correct 52 ms 9272 KB Output is correct
15 Correct 290 ms 18684 KB Output is correct
16 Correct 51 ms 10008 KB Output is correct
17 Correct 309 ms 20444 KB Output is correct
18 Correct 438 ms 29280 KB Output is correct
19 Correct 207 ms 20260 KB Output is correct
20 Correct 306 ms 20312 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 38 ms 6232 KB Output is correct
4 Correct 285 ms 22920 KB Output is correct
5 Correct 314 ms 21084 KB Output is correct
6 Correct 326 ms 20052 KB Output is correct
7 Correct 348 ms 20080 KB Output is correct
8 Correct 339 ms 20308 KB Output is correct
9 Correct 351 ms 24304 KB Output is correct
10 Correct 291 ms 21072 KB Output is correct
11 Correct 385 ms 38228 KB Output is correct
12 Correct 178 ms 19792 KB Output is correct
13 Correct 407 ms 33008 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 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 2392 KB Output is correct
2 Correct 0 ms 2492 KB Output is correct
3 Incorrect 0 ms 2396 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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -