oj.uz

Submission #823687

# Submission time Handle Problem Language Result Execution time Memory
823687 2023-08-13T00:58:02 Z GusterGoose27 Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 42536 KB 
#pragma GCC optimize("Ofast")
 
#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 reset(bool tp) {
		lz = 0;
		if (lp < rp) {
			l->reset(tp);
			r->reset(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() {
		if (l) {
			delete l;
			delete r;
		}
	}
};
 
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(0, n-1, 0); // 0s to the left
	tree[1] = new stree(0, n-1, 1); // 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;
}

Compilation message

plants.cpp: In function 'bool before(int, int)':
plants.cpp:142:1: warning: control reaches end of non-void function [-Wreturn-type]
  142 | }
      | ^

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 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 910 ms 3056 KB Output is correct
7 Execution timed out 4091 ms 6604 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
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 1 ms 212 KB Output is correct
5 Correct 13 ms 324 KB Output is correct
6 Correct 3195 ms 536 KB Output is correct
7 Execution timed out 4062 ms 4016 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
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 1 ms 212 KB Output is correct
5 Correct 13 ms 324 KB Output is correct
6 Correct 3195 ms 536 KB Output is correct
7 Execution timed out 4062 ms 4016 KB Time limit exceeded
8 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 Correct 0 ms 212 KB Output is correct
3 Execution timed out 4059 ms 3020 KB Time limit exceeded
4 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 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 Correct 5 ms 212 KB Output is correct
6 Correct 221 ms 360 KB Output is correct
7 Execution timed out 4056 ms 852 KB Time limit exceeded
8 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 Correct 794 ms 496 KB Output is correct
6 Execution timed out 4064 ms 42536 KB Time limit exceeded
7 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 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 910 ms 3056 KB Output is correct
7 Execution timed out 4091 ms 6604 KB Time limit exceeded
8 Halted 0 ms 0 KB -