oj.uz

Submission #823678

# Submission time Handle Problem Language Result Execution time Memory
823678 2023-08-13T00:38:28 Z GusterGoose27 Comparing Plants (IOI20_plants) C++17
44 / 100
 708 ms 43788 KB 
#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+5;
const int inf = 1e9;
int R[MAXN];
int n;

typedef pair<int, int> pii;

pii operator+(pii a, pii b) {
	return pii(a.first+b.first, a.second+b.second);
}

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	int mn;
	int lz = 0;
	stree(int lp, int rp, bool tp) : lp(lp), rp(rp) {
		if (lp < rp) {
			int md = (lp+rp)/2;
			l = new stree(lp, md, tp);
			r = new stree(md+1, rp, tp);
			mn = min(l->mn, r->mn);
		}
		else mn = tp ? R[lp] : inf;
	}
	void activate(int p) {
		if (lp > p || rp < p) return;
		if (lp == rp) {
			mn = lz;
			return;
		}
		prop();
		l->activate(p);
		r->activate(p);
		mn = min(l->mn, r->mn);
	}
	void set_lz(int p) {
		lz += p;
		mn += p;
	}
	void prop() {
		assert(l);
		l->set_lz(lz);
		r->set_lz(lz);
		lz = 0;
	}
	int find() { // finds a position that is 0
		if (mn > 0) return -1;
		if (lp == rp) return lp;
		prop();
		int lq = l->find();
		if (lq >= 0) return lq;
		int v = r->find();
		assert(v >= 0);
		return v;
	}
	void del(int p) { // can be absorbed into find
		if (lp > p || rp < p) return;
		if (lp == rp) {
			mn = inf;
			return;
		}
		prop();
		l->del(p); r->del(p);
		mn = min(l->mn, r->mn);
	}
	void upd(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			set_lz(v);
			return;
		}
		prop();
		l->upd(lv, rv, v);
		r->upd(lv, rv, v);
		mn = min(l->mn, r->mn);
	}
};

stree *tree[2];

int pos[MAXN];

void init(int k, vector<int> r) {
	n = r.size();
	for (int i = 0; i < n; i++) {
		R[i] = r[i];
	}
	tree[0] = new stree(0, n-1, 0); // 0s to the left
	tree[1] = new stree(0, n-1, 1); // rval
	// for (int i = 0; i < n; i++) {
		// if (r[i] == 0) {
			// tree[0]->upd(i+1, min(n-1, i+k-1), pii(1, 0));
			// if (i+k-1 >= n) tree[0]->upd(0, i+k-1-n, pii(1, 0));
		// }
	// }
	for (int i = 0; i < n; i++) {
		int f1;
		while ((f1 = tree[1]->find()) >= 0) {
			tree[0]->activate(f1);
			tree[1]->del(f1);
			tree[0]->upd(f1+1, min(n-1, f1+k-1), 1);
			if (f1+k-1 >= n) tree[0]->upd(0, f1+k-1-n, 1);
		}
		int v = tree[0]->find();
		assert(v != -1);
		tree[0]->del(v);
		pos[v] = i;
		tree[0]->upd(v+1, min(n-1, v+k-1), -1);
		tree[0]->upd(0, v+k-1-n, -1);
		tree[1]->upd(max(0, v-k+1), v-1, -1);
		if (v-k+1 < 0) tree[1]->upd(n+v-k+1, n-1, -1);
	}
	return;
}

int compare_plants(int x, int y) {
	return 2*(pos[x]<pos[y])-1;
	// if (x != (y+1)%n && y != (x+1)%n) return 0;
	// if (x == (y+1)%n) return 2*(!lt[y])-1;
	// return 2*lt[x]-1;
	// if (x < y) {
	// 	if (pre[y]-pre[x] == y-x) return -1;
	// 	if (pre[x+n]-pre[y] == x+n-y) return 1;
	// 	if (pre[y]-pre[x] == 0) return 1;
	// 	if (pre[x+n]-pre[y] == 0) return -1;
	// 	return 0;
	// // }
	return 0;
}

Subtask #1
0 / 5.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 1 ms 212 KB Output is correct
4 Incorrect 0 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 212 KB Output is correct
6 Correct 3 ms 576 KB Output is correct
7 Correct 50 ms 4588 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 49 ms 4564 KB Output is correct
11 Correct 46 ms 4464 KB Output is correct
12 Correct 46 ms 4604 KB Output is correct
13 Correct 55 ms 4512 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 212 KB Output is correct
6 Correct 3 ms 576 KB Output is correct
7 Correct 50 ms 4588 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 49 ms 4564 KB Output is correct
11 Correct 46 ms 4464 KB Output is correct
12 Correct 46 ms 4604 KB Output is correct
13 Correct 55 ms 4512 KB Output is correct
14 Correct 76 ms 7568 KB Output is correct
15 Correct 708 ms 43780 KB Output is correct
16 Correct 77 ms 7536 KB Output is correct
17 Correct 695 ms 43780 KB Output is correct
18 Correct 336 ms 43684 KB Output is correct
19 Correct 351 ms 43768 KB Output is correct
20 Correct 554 ms 43788 KB Output is correct

Subtask #4
17.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 Correct 44 ms 3872 KB Output is correct
4 Correct 305 ms 43460 KB Output is correct
5 Correct 356 ms 43568 KB Output is correct
6 Correct 611 ms 43568 KB Output is correct
7 Correct 695 ms 43568 KB Output is correct
8 Correct 684 ms 43564 KB Output is correct
9 Correct 334 ms 43684 KB Output is correct
10 Correct 315 ms 43568 KB Output is correct
11 Correct 263 ms 43516 KB Output is correct
12 Correct 304 ms 43456 KB Output is correct
13 Correct 347 ms 43476 KB Output is correct

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 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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -