Submission #827558

#	Time	Username	Problem	Language	Result	Execution time	Memory
827558		amunduzbaev	Comparing Plants (IOI20_plants)	C++17	44 / 100	1111 ms	33428 KiB

plants

#include "plants.h"

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

#define ar array
typedef long long ll;
//~ #define int ll

const int inf = 1e9;
const int N = 2e5 + 5;

struct ST{
	ar<ll, 2> tree[N << 2];
	ll f[N << 2];
	
	void build(int lx, int rx, int x){
		if(lx == rx) { tree[x][1] = lx; return; };
		int m = (lx + rx) >> 1;
		build(lx, m, x << 1), build(m + 1, rx, x << 1 | 1);
		tree[x][1] = lx;
	}
	
	ST(){
		build(0, N, 1);
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		tree[x << 1][0] += f[x];
		tree[x << 1 | 1][0] += f[x];
		f[x << 1] += f[x], f[x << 1 | 1] += f[x];
		f[x] = 0;
	}
	
	void add(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x][0] += v;
			f[x] += v;
			return;
		}
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, x << 1), add(l, r, v, m + 1, rx, x << 1 | 1);
		tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
	}
	
	void add(int l, int r, int v) { return add(l, r, v, 0, N, 1); }
	
	ar<ll, 2> get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return {inf, inf};
		if(lx >= l && rx <= r) return tree[x];
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		return min(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
	
	ar<ll, 2> get(int l, int r){
		return get(l, r, 0, N, 1);
	}
}tree, R;

vector<int> a;
int n;

void init(int k, vector<int> r) {
	
	n = r.size();
	a.resize(n);
	
	{
		int cnt = 0;
		for(int i=0;i<k - 1;i++) cnt += (r[i] == 0);
		for(int i=k - 1;;){
			tree.add(i, i, r[i] + cnt);
			
			if(r[i]){
				R.add(i, i, r[i]);
			} else {
				R.add(i, i, inf);
			}
			
			cnt -= (r[(i + n - k + 1) % n] == 0);
			cnt += (r[i] == 0);
			i = (i + 1) % n;
			if(i == k - 1) break;
		}
	}
	
	for(int j=n;j>0;j--){
		//~ for(int i=0;i<n;i++) cout<<tree.get(i, i)[0]<<" ";
		//~ cout<<"\n";
		
		auto [v, p] = tree.get(0, n - 1);
		
		assert(v == 0);
		
		a[p] = j;
		R.add(p, p, inf);
		tree.add(p, p, inf);
		{
			int l = p - k + 1, r = p;
			tree.add(max(l, 0), r, -1);
			R.add(max(l, 0), r, -1);
			if(l < 0) tree.add(n + l, n - 1, -1);
			if(l < 0) R.add(n + l, n - 1, -1);
			
			ar<ll, 2> pp = R.get(0, n - 1);
			while(pp[0] == 0){
				R.add(pp[1], pp[1], inf);
				{
					int l = pp[1] + 1, r = pp[1] + k - 1;
					tree.add(l, min(r, n - 1), 1);
					if(n <= r) tree.add(0,  r - n, 1);
				}
				pp = R.get(0, n - 1);
			}
		}
		{
			int l = p, r = p + k - 1;
			tree.add(l, min(r, n - 1), -1);
			if(n <= r) tree.add(0,  r - n, -1);
		}
	}
	
	return;
}

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