Submission #826927

#	Time	Username	Problem	Language	Result	Execution time	Memory
826927		tomruk	Comparing Plants (IOI20_plants)	C++17	14 / 100	4050 ms	3788 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
struct SegTree{
	vector<pair<int,int>> t;
	vector<int> lazy;
	int n;
	SegTree(int sz,vector<int> a){
		n = sz;
		t.assign(4*n,{0,0});
		lazy.assign(4*n,0);
		build(1,0,n-1,a);
	}
	void build(int v,int tl,int tr,vector<int> &a){
		if(tl == tr){
			t[v] = {a[tl],tl};
			return;
		}
		int tm = (tl + tr)/2;
		build(v*2,tl,tm,a);
		build(v*2 + 1,tm+1,tr,a);
		t[v] = t[v*2];
		if(t[v*2 + 1].first < t[v].first)
			t[v] = t[v*2+1];
	}
	void push(int v){
		t[v*2].first += lazy[v];
		lazy[v*2] += lazy[v];
		t[v*2 + 1].first += lazy[v];
		lazy[v*2 + 1] += lazy[v];
		lazy[v] = 0;
	}
	void upd(int v,int tl,int tr,int l,int r,int val){
		if(tr < l || r < tl)
			return;
		if(l <= tl && tr <= r){
			t[v].first += val;
			lazy[v] += val;
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val);
		upd(v * 2 + 1,tm+1,tr,l,r,val);
		t[v] = t[v*2];
		if(t[v*2 + 1].first < t[v].first)
			t[v] = t[v*2+1];
	}
	pair<int,int> get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl)
			return {1e9,0};
		if(l <= tl && tr <= r){
			return t[v];
		}
		push(v);
		int tm = (tl + tr)/2;
		auto a = get(v*2,tl,tm,l,r);
		auto b = get(v*2+1,tm+1,tr,l,r);
		if(b.first < a.first)
			return b;
		return a;
	}
	void upd(int l,int r,int val){
		upd(1,0,n-1,l,r,val);
	}
	pair<int,int> get(int l,int r){
		return get(1,0,n-1,l,r);
	}
};
int k;
int a[N];
void init(int k, vector<int> r) {
	int n  = r.size();
	SegTree t(n,r);
	// for(int i = n-1;i>=0;i--){
	// 	auto p1 = t.get(0,n-1);
	// 	auto p2 = t.get(p1.second + k,n-1);
	// 	if(p2.first == 0)
	// 		p1 = p2;
	// 	assert(p1.first == 0);
	// 	a[p1.second] = i;
	// 	if(p1.second)
	// 		t.upd(max(0,p1.second-k + 1),p1.second - 1,-1);
	// 	if(p1.second - k + 1 < 0){
	// 		t.upd(p1.second-k + 1 + n,n-1,-1);
	// 	}
	// 	t.upd(p1.second,p1.second,1e9);
	// 	// for(int j = 0;j<=n-1;j++){
	// 	// 	cout << t.get(j,j).first << ' ';
	// 	// }
	// 	// cout << endl;
	// 	// cout << i << ' ' << p1.second << endl;
	// }
	for(int i = n-1;i>=0;){
		vector<int> p;
		for(int j = 0;j<n;j++){
			if(t.get(j,j).first == 0)
				p.push_back(j);
		}
		vector<int> tmp;
		int maxi = -1e9;
		for(auto u:p){
			if(tmp.empty() || maxi + k - 1 < u)
				tmp.push_back(u);
			maxi = u;
		}
		int x = tmp.back() + k-1 - n;
		p.clear();
		for(auto u:tmp){
			if(u <= x)
				continue;
			p.push_back(u);
		}
		assert(p.size());
		for(auto u:p){
			if(u)
				t.upd(max(0,u-k + 1),u - 1,-1);
			if(u - k + 1 < 0){
				t.upd(u-k + 1 + n,n-1,-1);
			}
			t.upd(u,u,1e9);
			a[u] = i;
		}
		i -= p.size();
	}
}

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

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