oj.uz

Submission #304042

# Submission time Handle Problem Language Result Execution time Memory
304042 2020-09-21T01:37:02 Z myungwoo Comparing Plants (IOI20_plants) C++17
44 / 100
 891 ms 20076 KB 
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

#define MAXN 200005
#define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr);

int N, K, R[MAXN];
int A[MAXN], B[MAXN];

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;
	}
};

void get(int pos[])
{
	SegTree<int> segtree(R);
	ZeroContainer zc;
	for (int ord=1;ord<=N;ord++){
		for (;;){
			int p = segtree.findzero(1);
			if (!p) break;
			zc.insert(p);
			segtree.update(1, p, p, 1e9);
		}
		int x = zc.pop_smallest();
		pos[x] = ord; // perm[ord] = x
		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);
	}
}

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

int compare_plants(int x, int y)
{
	if (A[x+1] > A[y+1]) return -compare_plants(y, x);
	x++; y++;
	if ((A[x] < A[y]) != (B[x] < B[y])) return 1;
	return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 86 ms 3424 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 87 ms 3424 KB Output is correct
11 Correct 81 ms 3444 KB Output is correct
12 Correct 81 ms 3516 KB Output is correct
13 Correct 88 ms 3424 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 86 ms 3424 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 87 ms 3424 KB Output is correct
11 Correct 81 ms 3444 KB Output is correct
12 Correct 81 ms 3516 KB Output is correct
13 Correct 88 ms 3424 KB Output is correct
14 Correct 137 ms 4168 KB Output is correct
15 Correct 866 ms 10740 KB Output is correct
16 Correct 136 ms 4164 KB Output is correct
17 Correct 881 ms 10800 KB Output is correct
18 Correct 667 ms 14584 KB Output is correct
19 Correct 684 ms 15336 KB Output is correct
20 Correct 842 ms 10740 KB Output is correct

Subtask #4
17.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 74 ms 3252 KB Output is correct
4 Correct 569 ms 13804 KB Output is correct
5 Correct 621 ms 11372 KB Output is correct
6 Correct 745 ms 10740 KB Output is correct
7 Correct 859 ms 10740 KB Output is correct
8 Correct 891 ms 10860 KB Output is correct
9 Correct 584 ms 12408 KB Output is correct
10 Correct 612 ms 11628 KB Output is correct
11 Correct 523 ms 19496 KB Output is correct
12 Correct 578 ms 20076 KB Output is correct
13 Correct 648 ms 16536 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -