Submission #1064795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064795		n1k	Comparing Plants (IOI20_plants)	C++17	44 / 100	2595 ms	31284 KiB

plants

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

using namespace std;

using ll = long long;

struct E {
	ll x = 1e15, lz=0;
	E(){};
	E(ll xx){x=xx;};
	friend E operator+(E a, E b){
		return min(a.x, b.x);
	}
	void aply(ll add){
		x+=add;
		lz+=add;
	}
};

struct node{
	int lb, rb;
	E x;
	node *l=nullptr, *r=nullptr;
	bool ext(){
		if(lb<rb and not l){
			int mb = (lb + rb) / 2;
			l = new node{lb, mb}, r = new node{mb+1, rb};
		}
		// push
		if(l){
			l->x.aply(x.lz);
			r->x.aply(x.lz);
			x.lz=0;
		}
		return l;
	}
	E qry(int lo, int hi){
		if(hi<lb or rb<lo) return E();
		if(lo<=lb and rb<=hi) return x;
		if(ext()) {
			E y = l->qry(lo, hi) + r->qry(lo, hi);
			return y;
		}
		return E();
	}
	void upd(int lo, int hi, ll add){
		if(hi<lb or rb<lo) return;
		if(lo<=lb and rb<=hi) {
			x.aply(add);
			return;
		}
		if(ext()) {
			l->upd(lo, hi, add), r->upd(lo, hi, add);
			x = l->x + r->x;
		}
	}
	void bld(vector<int> &v){
		if(lb==rb) x.x = v[lb];
		if(ext()) {
			l->bld(v), r->bld(v);
			x = l->x + r->x;
		}
	}
};

vector<int> h1, h2;
vector<vector<int>> jl, jr;
int K;

void init(int k, std::vector<int> r) {
	K = k;
	int n = r.size(), t=n;
	node seg{0, n-1};
	h1.assign(n, 0);
	h2.assign(n, 0);

	auto find = [&](int lb, int rb){
		while(lb<rb){
			int mb = (lb+rb+1)/2;
			if(seg.qry(mb, rb).x==0){
				lb=mb;
			}else{
				rb=mb-1;
			}
		}
		return seg.qry(lb, lb).x==0 ? lb : int(-1e9);
	};
	auto findfirst = [&](int lb, int rb){
		while(lb<rb){
			int mb = (lb+rb)/2;
			if(seg.qry(lb, mb).x==0){
				rb=mb;
			}else{
				lb = mb + 1;
			}
		}
		return seg.qry(lb, lb).x==0 ? lb : int(-1e9);
	};
	function<void(int, vector<int>& )> get = [&](int id, vector<int> &h){
		// find 0 in range (id-k+1, id-1)
		// if (id-k+1)<0
		int lb = id - k + 1, rb = id-1;

		while(1){
			int nid = -1e9;
			if(rb>=0){
				nid = max(nid, find(max(lb, 0), rb));
			}if(lb<0 and nid<0){
				nid=max(nid, find((lb+n)%n, n-1));
			}

			if(nid>=0)
				get(nid, h);
			else
				break;
		}
		if(rb>=0){
			seg.upd(max(lb, 0), rb, -1);
		}if(lb<0){
			seg.upd((lb+n)%n, n-1, -1);
		}
		seg.upd(id, id, 1e9);
		h[id]=t--;
	};
	/*
	seg.bld(r);
	while(find(0, n-1)>=0){
		get(find(0, n-1), h1);
	}
	*/
	t=n;
	seg.bld(r);
	while(findfirst(0, n-1)>=0){
		get(findfirst(0, n-1), h2);
	}
	//for(auto x:h1) cerr<< x << " "; cerr<<endl;
	//for(auto x:h2) cerr<< x << " "; cerr<<endl;
}

int compare_plants(int x, int y) {
	if( h2[x]>h2[y]) return 1;
	if( h2[x]<h2[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