Submission #304042

#	Time	Username	Problem	Language	Result	Execution time	Memory
304042		myungwoo	Comparing Plants (IOI20_plants)	C++17	44 / 100	891 ms	20076 KiB

plants

#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 (stderr)

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
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25