oj.uz

답안 #823693

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
823693 2023-08-13T01:11:13 Z GusterGoose27 식물 비교 (IOI20_plants) C++17
11 / 100
 3587 ms 5452 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) {
		if (lp > p || rp < p) return;
		// ulz += lz[cur];
		if (lp == rp) {
			mn[cur] = lz[cur];
			return;
		}
		// prop(cur);
		int md = (lp+rp)/2;
		activate(p, 2*cur, lp, md);
		activate(p, 2*cur+1, md+1, rp);
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1425 ms 3060 KB Output is correct
7 Runtime error 34 ms 5452 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 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 0 ms 212 KB Output is correct
5 Correct 12 ms 332 KB Output is correct
6 Runtime error 2 ms 596 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 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 0 ms 212 KB Output is correct
5 Correct 12 ms 332 KB Output is correct
6 Runtime error 2 ms 596 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 30 ms 5196 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 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 Correct 6 ms 212 KB Output is correct
6 Correct 125 ms 368 KB Output is correct
7 Correct 3405 ms 852 KB Output is correct
8 Correct 2824 ms 1056 KB Output is correct
9 Correct 2976 ms 1164 KB Output is correct
10 Correct 2892 ms 1164 KB Output is correct
11 Correct 3218 ms 1168 KB Output is correct
12 Correct 2850 ms 1164 KB Output is correct
13 Correct 3587 ms 1164 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 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 0 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1425 ms 3060 KB Output is correct
7 Runtime error 34 ms 5452 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -