Submission #301566

#	Time	Username	Problem	Language	Result	Execution time	Memory
301566		Yousef_Salama	Comparing Plants (IOI20_plants)	C++17	100 / 100	1386 ms	84188 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

struct segment_tree{
	int n;
	vector <int> tree, flag;
	
	void build(int i, int L, int R, const vector <int>& v){
		if(L == R){
			tree[i] = v[L];
			return;
		}
		
		int mid = (L + R) / 2;
		
		build(2 * i, L, mid, v);
		build(2 * i + 1, mid + 1, R, v);
		
		tree[i] = min(tree[2 * i], tree[2 * i + 1]);
	}
	segment_tree(const vector <int>& v){
		n = v.size();
		tree.resize(4 * n);
		flag.resize(4 * n, 0);
		
		build(1, 0, n - 1, v);
	}
	
	void push(int i, int L, int R){
		if(L < R){
			flag[2 * i] += flag[i];
			flag[2 * i + 1] += flag[i];
		}
		
		tree[i] += flag[i];
		flag[i] = 0;
	}
	
	void update(int i, int L, int R, int u, int v, int val){
		push(i, L, R);
		
		if(R < u || v < L)return;
		if(u <= L && R <= v){
			flag[i] += val;
			push(i, L, R);
			
			return;
		}
		
		int mid = (L + R) / 2;
		
		update(2 * i, L, mid, u, v, val);
		update(2 * i + 1, mid + 1, R, u, v, val);
		
		tree[i] = min(tree[2 * i], tree[2 * i + 1]);
	}
	void update(int u, int v, int val){
		update(1, 0, n - 1, u, v, val);
	}
	
	int extract_zero(int i, int L, int R){
		push(i, L, R);
		
		if(tree[i] != 0)return -1;
		
		if(L == R){
			tree[i] = 1 << 30;
			return L;
		}
		
		int mid = (L + R) / 2;
		
		push(2 * i, L, mid);
		push(2 * i + 1, mid + 1, R);
		
		int r;
		if(tree[2 * i] == 0){
			r = extract_zero(2 * i, L, mid);
		}else{
			r = extract_zero(2 * i + 1, mid + 1, R);
		}
		
		tree[i] = min(tree[2 * i], tree[2 * i + 1]);
		
		return r;
	}
	int extract_zero(){
		return extract_zero(1, 0, n - 1);
	}
};

const int LOG = 20;

vector < vector <int> > next_greater, next_smaller;
vector <int> v;
int n, k;

void init(int pk, vector <int> r){
	n = r.size();
	k = pk;

	for(int i = 0; i < n; i++)
		r[i] = k - 1 - r[i];
	
	segment_tree tree(r);
	set <int> s;
	set < pair <int, int> > d;
	
	auto dist = [&](int x, int y){
					if(x > y)return x - y;
					return x - y + n;
				};
	auto add = [&](int i){
					if(s.empty()){
						s.insert(i);
						d.insert({n, i});
						return;
					}
					
					auto ptr = s.insert(i).first;
					auto r = (next(ptr) == s.end() ? s.begin() : next(ptr)), l = (ptr == s.begin() ? prev(s.end()) : prev(ptr));
					
					d.erase({dist(*r, *l), *r});
					d.insert({dist(*r, i), *r});
					d.insert({dist(i, *l), i});
				};
	auto del = [&](int i){
					if(s.size() == 1){
						s.clear();
						d.clear();
						return;
					}
					
					auto ptr = s.find(i);
					auto r = (next(ptr) == s.end() ? s.begin() : next(ptr)), l = (ptr == s.begin() ? prev(s.end()) : prev(ptr));
					
					d.insert({dist(*r, *l), *r});
					d.erase({dist(*r, i), *r});
					d.erase({dist(i, *l), i});
						
					s.erase(ptr);
				};
	
	v.resize(2 * n);	
	for(int i = 0; i < n; i++){
		while(true){
			int r = tree.extract_zero();
			if(r == -1)break;
			
			add(r);
		}
		
		int x = d.rbegin()->second;
		del(x);
		
		if(x - (k - 1) >= 0){
			tree.update(x - (k - 1), x - 1, -1);
		}else{
			if(x > 0)tree.update(0, x - 1, -1);
			tree.update(x - (k - 1) + n, n - 1, -1);
		}
		v[x] = i;
	}
	
	for(int i = n; i < 2 * n; i++)
		v[i] = v[i - n];
	
	next_greater.resize(LOG, vector <int>(2 * n));
	next_smaller.resize(LOG, vector <int>(2 * n));
	
	set < pair <int, int> > q;
	for(int i = 2 * n - 1; i >= 0; i--){
		if(i + k < 2 * n){
			q.erase({v[i + k], i + k});
		}
		
		auto x = q.lower_bound(make_pair(v[i], 0));
		
		if(x != q.end())next_greater[0][i] = x->second;
		else next_greater[0][i] = -1;
		
		if(x != q.begin())next_smaller[0][i] = prev(x)->second;
		else next_smaller[0][i] = -1;
		
		for(int j = 1; j < LOG; j++){
			if(next_greater[j - 1][i] == -1)next_greater[j][i] = -1;
			else next_greater[j][i] = next_greater[j - 1][next_greater[j - 1][i]];
			
			if(next_smaller[j - 1][i] == -1)next_smaller[j][i] = -1;
			else next_smaller[j][i] = next_smaller[j - 1][next_smaller[j - 1][i]];
		}
		
		q.insert({v[i], i});
	}
	
	/*for(int i = 0; i < n; i++)
		cout << r[i] << ' ';
	cout << endl;
	for(int i = 0; i < n; i++)
		cout << v[i] << ' ';
	cout << endl;*/
}

int compare_plants(int x, int y){
	auto go_greater = [&](int x, int y){
							for(int l = LOG - 1; l >= 0; l--){
								if(next_greater[l][x] != -1 && next_greater[l][x] <= y){
									x = next_greater[l][x];
								}
							}
							
							if(v[x] > v[y] || x + k <= y)return false;
							return true;
						};
					
	auto go_smaller = [&](int x, int y){
							for(int l = LOG - 1; l >= 0; l--){
								if(next_smaller[l][x] != -1 && next_smaller[l][x] <= y){
									x = next_smaller[l][x];
								}
							}
							
							if(v[x] < v[y] || x + k <= y)return false;
							return true;
						};
						
	if(v[x] < v[y]){
		if(go_greater(x, y) || go_smaller(y, x + n))return -1;
		return 0;
	}else{
		if(go_smaller(x, y) || go_greater(y, x + n))return 1;
		return 0;
	}
}

/*
int main(){
	init(2, {1, 0, 1, 1, 0});
	cout << compare_plants(0, 2) << endl;
	cout << compare_plants(1, 2) << endl;

	return 0;
}
*/

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25