oj.uz

Submission #823692

# Submission time Handle Problem Language Result Execution time Memory
823692 2023-08-13T01:09:14 Z GusterGoose27 Comparing Plants (IOI20_plants) C++17
0 / 100
 1430 ms 5436 KB 
#pragma GCC optimize("Ofast")

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+5;
const int SZ = 512;
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[2*SZ];
	int lz[2*SZ];
	stree() {}
	void reset(bool tp) {
		memset(lz, 0, sizeof(int)*2*SZ);
		for (int i = SZ; i < 2*SZ; i++) {
			mn[i] = (tp && i < SZ+n) ? R[i-SZ] : inf;
		}
		for (int i = SZ-1; i > 0; i--) mn[i] = min(mn[2*i], mn[2*i+1]);
	}
	void activate(int p, int cur = 1, int lp = 0, int rp = SZ-1, int ulz = 0) {
		if (lp > p || rp < p) return;
		ulz += lz[cur];
		if (lp == rp) {
			mn[cur] = ulz;
			return;
		}
		// prop(cur);
		int md = (lp+rp)/2;
		activate(p, 2*cur, lp, md, ulz);
		activate(p, 2*cur+1, md+1, rp, ulz);
		mn[cur] = min(mn[2*cur], mn[2*cur+1])+lz[cur];
	}
	void set_lz(int cur, int p) {
		lz[cur] += p;
		mn[cur] += p;
	}
	// void prop(int cur) {
	// 	assert(cur < SZ);
	// 	set_lz(2*cur, lz[cur]);
	// 	set_lz(2*cur+1, lz[cur]);
	// 	lz[cur] = 0;
	// }
	int find(int cur = 1, int lp = 0, int rp = SZ-1, int ulz = 0) { // finds a position that is 0
		if (mn[cur]+ulz > 0) return -1;
		if (lp == rp) {
			mn[cur] = inf;
			return lp;
		}
		ulz += lz[cur];
		// prop(cur);
		int md = (lp+rp)/2;
		int lq = find(2*cur, lp, md, ulz);
		if (lq >= 0) {
			mn[cur] = min(mn[2*cur], mn[2*cur+1])+lz[cur];
			return lq;
		}
		int v = find(2*cur+1, md+1, rp, ulz);
		assert(v >= 0);
		mn[cur] = min(mn[2*cur], mn[2*cur+1])+lz[cur];
		return v;
	}
	// void del(int p, int cur = 1, int lp = 0, int rp = SZ-1) { // can be absorbed into find
	// 	if (lp > p || rp < p) return;
	// 	if (lp == rp) {
	// 		mn[cur] = inf;
	// 		return;
	// 	}
	// 	prop(cur);
	// 	int md = (lp+rp)/2;
	// 	del(p, 2*cur, lp, md); del(p, 2*cur+1, md+1, rp);
	// 	mn[cur] = min(mn[2*cur], mn[2*cur+1]);
	// }
	void upd(int lv, int rv, int v, int cur = 1, int lp = 0, int rp = SZ-1) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			set_lz(cur, v);
			return;
		}
		// ulz += lz[cur];
		// prop(cur);
		int md = (lp+rp)/2;
		upd(lv, rv, v, 2*cur, lp, md);
		upd(lv, rv, v, 2*cur+1, md+1, rp);
		mn[cur] = min(mn[2*cur], mn[2*cur+1])+lz[cur];
	}
};

stree *tree[2];
int k;

void init(int K, vector<int> r) {
	k = K;
	n = r.size();
	assert(n <= 300);
	for (int i = 0; i < n; i++) {
		R[i] = r[i];
	}
	tree[0] = new stree(); // 0s to the left
	tree[1] = new stree(); // rval
}

bool before(int x, int y) { // could x be taller than y
	tree[0]->reset(0);
	tree[1]->reset(1);
	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();
		// tree[0]->del(v);
		if (v == -1) return 0;
		if (v == x) return 1;
		if (v == y) {
			continue;
		}
		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);
	}
	assert(false);
}

int compare_plants(int x, int y) {
	bool a = before(x, y);
	bool b = !before(y, x);
	// delete tree[0];
	// delete tree[1];
	return a+b-1;
	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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1430 ms 3024 KB Output is correct
7 Runtime error 32 ms 5436 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

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

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 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 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 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 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Runtime error 1 ms 480 KB Execution killed with signal 6
6 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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1430 ms 3024 KB Output is correct
7 Runtime error 32 ms 5436 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -