oj.uz

답안 #823699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
823699 2023-08-13T01:38:02 Z GusterGoose27 식물 비교 (IOI20_plants) C++17
15 / 100
 544 ms 19492 KB 
#pragma GCC optimize("Ofast")

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

using namespace std;

const int MAXN = 2e5+5;
const int SZ = 1<<18;
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 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;
		if (lp == rp) {
			mn[cur] = lz[cur];
			return;
		}
		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;
	}
	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];
		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 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;
		}
		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];
	}
	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;
		}
		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])+lz[cur];
	}
	int rt_zero(int lv, int cur = 1, int lp = 0, int rp = SZ-1, int ulz = 0) {
		if (rp < lv || mn[cur]+ulz > 0) return n;
		if (lp == rp) {
			return lp;
		}
		ulz += lz[cur];
		int md = (lp+rp)/2;
		int lq = rt_zero(lv, 2*cur, lp, md, ulz);
		if (lq < n) return lq;
		return rt_zero(lv, 2*cur+1, md+1, rp, ulz);
	}
};

stree *tree[2];
int k;

int before[MAXN]; // 0 => 1, 1 => 0, 2 => -1

// if strict, we don't allow x. Otherwise, we optimize for x

void make_strict() { // 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[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();
		if (v == -1) return;
		if (v == 0) continue;
		before[v]++;
		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;
	// assert(false);
}

void target(int cur = 0) { // we are trying to activate cur.
// because it is possible, we will never have a cycle
	before[cur]++;
	while (1) {
		int f1;
		while ((f1 = tree[1]->rt_zero(max(0, cur-k+1))) < cur) target(f1);
		if (cur-k+1 < 0) while ((f1 = tree[1]->rt_zero(n+cur-k+1)) < n) target(f1);
		int u = tree[1]->rt_zero(cur);
		if (u == n) u = tree[1]->rt_zero(0);
		if (u == cur) {
			tree[1]->upd(max(0, cur-k+1), cur-1, -1);
			if (cur-k+1 < 0) tree[1]->upd(n+cur-k+1, n-1, -1);
			tree[1]->del(cur);
			return;
		}
		else target(u);
	}
	assert(false);
}

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
	make_strict();
	tree[0]->reset(0);
	tree[1]->reset(1);
	target(0);
}

int compare_plants(int x, int y) {
	return 1-before[y];
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Incorrect 5 ms 8532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 5 ms 8476 KB Output is correct
3 Incorrect 5 ms 8492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 5 ms 8476 KB Output is correct
3 Incorrect 5 ms 8492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Incorrect 4 ms 8532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 5 ms 8536 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 5 ms 8532 KB Output is correct
5 Correct 6 ms 8504 KB Output is correct
6 Correct 227 ms 13952 KB Output is correct
7 Correct 393 ms 14516 KB Output is correct
8 Correct 77 ms 14860 KB Output is correct
9 Correct 544 ms 15188 KB Output is correct
10 Correct 238 ms 14720 KB Output is correct
11 Correct 156 ms 14928 KB Output is correct
12 Correct 212 ms 19492 KB Output is correct
13 Correct 227 ms 14928 KB Output is correct
14 Correct 146 ms 14804 KB Output is correct
15 Correct 409 ms 14904 KB Output is correct
16 Correct 215 ms 14380 KB Output is correct
17 Correct 239 ms 14552 KB Output is correct

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Incorrect 5 ms 8532 KB Output isn't correct
4 Halted 0 ms 0 KB -