oj.uz

Submission #304379

# Submission time Handle Problem Language Result Execution time Memory
304379 2020-09-21T08:26:40 Z myungwoo Comparing Plants (IOI20_plants) C++17
30 / 100
 1362 ms 78872 KB 
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

#define MAXN 200005
#define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr);
typedef pair<int, int> pii;

int N, K, R[MAXN];
int H[MAXN], _right[MAXN][18], _left[MAXN][18];

template <typename T>
struct SegTree{
	int n_bits, TS, ST;
	int range_l(int x){ return ((x<<(__builtin_clz(x)-31+n_bits)) ^ (1<<n_bits)) + 1; }
	int range_r(int x){ return ((x<<(__builtin_clz(x)-31+n_bits) ^ ((1<<(__builtin_clz(x)-31+n_bits))-1)) ^ (1<<n_bits)) + 1; }
	struct Value{
		T value, lazysum;
	};
	vector<Value> tree;
	SegTree(int arr[]){
		n_bits = 32-__builtin_clz(N-1);
		TS = 1 << n_bits+1; ST = TS/2-1;
		tree.resize(TS, {0, 0});
		for (int i=ST+1;i<TS;i++) tree[i].value = i-ST <= N ? arr[i-ST] : 1e9;
		for (int i=ST;i;i--) tree[i].value = min(tree[i*2].value, tree[i*2+1].value);
	}
	void propagate(int n){
		if (n <= ST){
			tree[n*2].value += tree[n].lazysum, tree[n*2+1].value += tree[n].lazysum;
			tree[n*2].lazysum += tree[n].lazysum, tree[n*2+1].lazysum += tree[n].lazysum;
		}
		tree[n].lazysum = 0;
	}
	void update(int n, int l, int r, const int &v){
		int s = range_l(n), e = range_r(n);
		if (l > r || e < l || r < s) return;
		if (l <= s && e <= r){
			tree[n].value += v, tree[n].lazysum += v;
			return;
		}
		propagate(n);
		update(n*2, l, r, v);
		update(n*2+1, l, r, v);
		tree[n].value = min(tree[n*2].value, tree[n*2+1].value);
	}
	int findzero(int n){
		if (tree[n].value != 0) return 0;
		propagate(n);
		if (n > ST) return n-ST;
		if (!tree[n*2].value) return findzero(n*2);
		else if (!tree[n*2+1].value) return findzero(n*2+1);
		else assert(0);
	}
};

struct ZeroContainer{
	set<int> pos, non_covered;
	set<int>::iterator _left(set<int>::iterator it){
		auto ret = it;
		if (ret == pos.begin()) ret = pos.end();
		return --ret;
	}
	set<int>::iterator _right(set<int>::iterator it){
		auto ret = it; ret++;
		if (ret == pos.end()) return pos.begin();
		return ret;
	}
	void insert(int p){
		auto it = pos.insert(p).first;
		auto l = _left(it), r = _right(it);
		if (l == it || (*it-*l+N)%N >= K) non_covered.insert(p);
		if (r != it && (*r-*it+N)%N < K) non_covered.erase(*r);
	}
	void remove(int p){
		auto it = pos.find(p);
		auto l = _left(it), r = _right(it);
		if (l != it && r != it && (l == r || (*r-*l+N)%N >= K)) non_covered.insert(*r);
		pos.erase(it);
	}
	int pop_smallest(){
		int ret = *non_covered.begin(); non_covered.erase(ret);
		remove(ret);
		return ret;
	}
};

int go_left(int n, int d)
{
	n -= d%N;
	if (n < 1) n += N;
	return n;
}

int go_right(int n, int d)
{
	n += d%N;
	if (n > N) n -= N;
	return n;
}

void init(int K, vector<int> r)
{
	::K = K;
	N = r.size();
	for (int i=1;i<=N;i++) R[i] = r[i-1];

	{
		SegTree<int> segtree(R);
		ZeroContainer zc;
		for (int ord=N;ord;ord--){
			for (;;){
				int p = segtree.findzero(1);
				if (!p) break;
				zc.insert(p);
				segtree.update(1, p, p, 1e9);
			}
			int x = zc.pop_smallest();
			H[x] = ord;
			segtree.update(1, max(1, x-K+1), x-1, -1);
			if (x-K+1 < 1) segtree.update(1, N-(1-(x-K+1))+1, N, -1);
		}
	}

	{
		set <pii> s;
		for (int i=1;i<=K;i++) s.insert({H[i], i});
		for (int i=1;i<=N;i++){
			auto it = s.lower_bound({H[i], 0});
			if (it != s.begin()){
				it--;
				_right[i][0] = (it->second - i + N) % N;
			}
			int t = (i+K-1)%N+1;
			s.insert({H[t], t});
			s.erase({H[i], i});
		}
	}
	{
		set <pii> s;
		for (int i=1;i<K;i++) s.insert({H[i], i});
		for (int i=1;i<=N;i++){
			int t = (i+K-2)%N+1;
			auto it = s.lower_bound({H[t], 0});
			if (it != s.begin()){
				it--;
				_left[t][0] = (t - it->second + N) % N;
			}
			s.insert({H[t], t});
			s.erase({H[i], i});
		}
	}
	// for (int i=1;i<=N;i++) debug("%d: %d %d\n", i, _right[i][0], _left[i][0]);
	for (int i=0;i+1<18;i++) for (int j=1;j<=N;j++){
		_left[j][i+1] = _left[go_left(j, _left[j][i])][i] + _left[j][i];
		_right[j][i+1] = _right[go_right(j, _right[j][i])][i] + _right[j][i];
	}
}

bool has_left_path(int a, int b)
{
	int d = (a-b+N)%N;
	for (int i=18;i--;) if (d >= _left[a][i]){
		d -= _left[a][i];
		a = go_left(a, _left[a][i]);
	}
	return (a-b+N)%N < K && H[a] >= H[b];
}

bool has_right_path(int a, int b)
{
	int d = (b-a+N)%N;
	for (int i=18;i--;) if (d >= _right[a][i]){
		d -= _right[a][i];
		a = go_right(a, _right[a][i]);
	}
	return (b-a+N)%N < K && H[a] >= H[b];
}

int compare_plants(int a, int b)
{
	a++; b++;
	if (has_left_path(a, b) || has_right_path(a, b)) return 1;
	if (has_left_path(b, a) || has_right_path(b, a)) return -1;
	return 0;
}

Compilation message

plants.cpp: In instantiation of 'SegTree<T>::SegTree(int*) [with T = int]':
plants.cpp:109:25:   required from here
plants.cpp:23:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   23 |   TS = 1 << n_bits+1; ST = TS/2-1;
      |             ~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 170 ms 3148 KB Output is correct
7 Correct 219 ms 6776 KB Output is correct
8 Correct 606 ms 39276 KB Output is correct
9 Correct 614 ms 38508 KB Output is correct
10 Correct 615 ms 38668 KB Output is correct
11 Correct 661 ms 39148 KB Output is correct
12 Correct 679 ms 39020 KB Output is correct
13 Correct 690 ms 43628 KB Output is correct
14 Correct 660 ms 34028 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 114 ms 4212 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 106 ms 4212 KB Output is correct
11 Correct 152 ms 4004 KB Output is correct
12 Correct 174 ms 4212 KB Output is correct
13 Correct 117 ms 4212 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 114 ms 4212 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 106 ms 4212 KB Output is correct
11 Correct 152 ms 4004 KB Output is correct
12 Correct 174 ms 4212 KB Output is correct
13 Correct 117 ms 4212 KB Output is correct
14 Correct 168 ms 6880 KB Output is correct
15 Runtime error 1362 ms 78872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 137 ms 3512 KB Output is correct
4 Correct 788 ms 37148 KB Output is correct
5 Correct 839 ms 34668 KB Output is correct
6 Correct 921 ms 34132 KB Output is correct
7 Correct 993 ms 34484 KB Output is correct
8 Runtime error 1196 ms 75704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 40 ms 1016 KB Output is correct
8 Correct 21 ms 1024 KB Output is correct
9 Correct 33 ms 1024 KB Output is correct
10 Correct 21 ms 1152 KB Output is correct
11 Correct 40 ms 1016 KB Output is correct
12 Correct 34 ms 1016 KB Output is correct
13 Correct 20 ms 1016 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 722 ms 34116 KB Output is correct
7 Correct 814 ms 34028 KB Output is correct
8 Correct 817 ms 34540 KB Output is correct
9 Runtime error 1097 ms 75740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 170 ms 3148 KB Output is correct
7 Correct 219 ms 6776 KB Output is correct
8 Correct 606 ms 39276 KB Output is correct
9 Correct 614 ms 38508 KB Output is correct
10 Correct 615 ms 38668 KB Output is correct
11 Correct 661 ms 39148 KB Output is correct
12 Correct 679 ms 39020 KB Output is correct
13 Correct 690 ms 43628 KB Output is correct
14 Correct 660 ms 34028 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 114 ms 4212 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 5 ms 640 KB Output is correct
24 Correct 106 ms 4212 KB Output is correct
25 Correct 152 ms 4004 KB Output is correct
26 Correct 174 ms 4212 KB Output is correct
27 Correct 117 ms 4212 KB Output is correct
28 Correct 168 ms 6880 KB Output is correct
29 Runtime error 1362 ms 78872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -