Submission #1145485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145485		PagodePaiva	Comparing Plants (IOI20_plants)	C++20	27 / 100	342 ms	14548 KiB

plants

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

using namespace std;

const int N = 200010;
int v[N];
int n;
int ans[N];

struct Segtree{
	int tree[4*N], lazy[4*N];
	int join(int a, int b){
		return min(a, b);
	}
	void build(int node, int l, int r){
		lazy[node] = 0;
		if(l == r){
			tree[node] = v[l];
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	void unlazy(int node, int l, int r){
		tree[node] += lazy[node];
		if(l != r){
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node] = 0;
	}
	void update(int node, int l, int r, int tl, int tr, int val){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return;
		if(l <= tl and tr <= r){
			lazy[node] += val;
			unlazy(node, tl, tr);
			return;
		}
		int mid = (tl+tr)/2;
		update(2*node, l, r, tl, mid, val);
		update(2*node+1, l, r, mid+1, tr, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return 1e8;
		if(l <= tl and tr <= r) return tree[node];
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
	}
	int busca(int node, int l, int r, int tl, int tr, int val){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return 1e8;
		if(l <= tl and tr <= r){
			if(tree[node] > val) return 1e8;
			if(tl == tr) return tl;
			int mid = (tl+tr)/2;
			unlazy(2*node, tl, mid);
			unlazy(2*node+1, mid+1, tr);
			if(tree[2*node] <= val) return busca(2*node, l, r, tl, mid, val);
			else return busca(2*node+1, l, r, mid+1, tr, val);
		}
		int mid = (tl+tr)/2;
		int d = busca(2*node, l, r, tl, mid, val);
		if(d != 1e8) return d;
		return busca(2*node+1, l, r, mid+1, tr, val);
	}
} seg;

int k;

int ask(int l, int r){
	if(l <= r) return seg.query(1, l, r, 0, n-1);
	return min(seg.query(1, l, n-1, 0, n-1), seg.query(1, 0, r, 0, n-1));
}

bool incluso(int x, int l, int r){
	if(l <= r){
		if(l <= x and x <= r) return true;
		return false;
	}
	else{
		if(l <= x and x <= n-1) return true;
		if(0 <= x and x <= r) return true;
		return false;
	}
}

struct Plants{
	set <int> idx;
	int answer;
	void build(){
		int l = 0, r = n-1;
		while(l <= r){
			int d = seg.busca(1, l, r, 0, n-1, 0);
			if(d == 1e8) break;
			idx.insert(d);
			l = d+1;
		}
		for(auto x : idx){
			if(ask(((x-k+1)+n)%n, x-1) != 0) answer = x;
		}
	}
	void run(int tt){
		/*cout << tt << ' ' << answer << ' ';
		for(auto x : idx){
			cout << x << ' ';
		}
		cout << endl;*/
		ans[answer] = tt;
		idx.erase(answer);
		seg.update(1, answer, answer, 0, n-1, 1e8);
		int r = answer, l = answer-k+1;
		if(l < 0) l += n;
		if(l <= r){
			seg.update(1, l, r, 0, n-1, -1);
			vector <int> add;
			while(l <= r){
				int d = seg.busca(1, l, r, 0, n-1, 0);
				if(d == 1e8) break;
				add.push_back(d);
				l = d+1;
			}
			if(add.empty()){
				if(idx.empty()) return;
				else if(idx.size() == 1){
					answer = *(idx.begin());
				}
				else{
					auto it = idx.upper_bound(answer);
					if(it == idx.end()) it = idx.begin();
					answer = *it;
				}
			}
			else{
				if(idx.empty()){
					answer = add[0];
					for(auto x : add) idx.insert(x);
				}
				else{
					auto it = idx.upper_bound(add.back());
					if(it == idx.end()) it = idx.begin();
					int valor = *it;
					if(incluso(add.back(), (valor-(k-1)+n)%n, valor)){
						answer = add[0];
					}
					else{
						answer = valor;
					}
					for(auto x : add){
						idx.insert(x);
					}
				}
			}
		}
		else{
			seg.update(1, l, n-1, 0, n-1, -1);
			seg.update(1, 0, r, 0, n-1, -1);
			vector <int> add;
			while(l <= n-1){
				int d = seg.busca(1, l, n-1, 0, n-1, 0);
				if(d == 1e8) break;
				add.push_back(d);
				l = d+1;
			}
			l = 0;
			while(l <= r){
				int d = seg.busca(1, l, r, 0, n-1, 0);
				if(d == 1e8) break;
				add.push_back(d);
				l = d+1;
			}
			if(add.empty()){
				if(idx.empty()) return;
				else if(idx.size() == 1){
					answer = *(idx.begin());
				}
				else{
					auto it = idx.upper_bound(answer);
					if(it == idx.end()) it = idx.begin();
					answer = *it;
				}
			}
			else{
				if(idx.empty()){
					answer = add[0];
					for(auto x : add) idx.insert(x);
				}
				else{
					auto it = idx.upper_bound(add.back());
					if(it == idx.end()) it = idx.begin();
					int valor = *it;
					if(incluso(add.back(), (valor-(k-1)+n)%n, valor)){
						answer = add[0];
					}
					else{
						answer = valor;
					}
					for(auto x : add){
						idx.insert(x);
					}
				}
			}
		}
	}
} plants;

void init(int kk, std::vector<int> r) {
	k = kk;
	n = r.size();
	for(int i = 0; i < r.size();i++){
		v[i] = r[i];
	}
	seg.build(1, 0, n-1);
	plants.build();
	for(int tt = n-1;tt >= 0;tt--){
		plants.run(tt);
	}
	for(int i = 0;i < n;i++){
	//	cout << ans[i] << ' ';
	}
	return;
}

int compare_plants(int x, int y) {
	if(ans[x] > ans[y]) return 1;
	return -1;
	return 0;
}

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