Submission #1064606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064606		n1k	Comparing Plants (IOI20_plants)	C++17	0 / 100	87 ms	5856 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> h;
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};
	seg.bld(r);
	h.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);
	};
	function<void(int)> get = [&](int id){
		// 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);
			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--;
	};
	while(find(0, n-1)>=0){
		//cerr << find(0, n-1) << endl;
		get(find(0, n-1));
		//for(int i=0; i<n; i++) cerr << seg.qry(i, i).x << " "; cout << endl;
	}
	//for(auto x:h) cerr << x-1 << " "; cerr<<endl;

	node best{0, n-1};
	vector<int> pos(n+1);
	for(int i=0; i<n; i++) pos[h[i]] = i;
	auto findbest = [&](int lb, int rb){
		// TODO: check query outside the tree
		ll cur = best.qry(lb, rb).x;
		if(rb>=n) {
			cur = min(cur, best.qry(0, rb%n).x);
		}if(lb<0){
			cur=min(cur, best.qry((lb+n)%n, n-1).x);
		}
		return cur;
	};
	jl.assign(n, vector<int>(20));
	jr.assign(n, vector<int>(20));
	for(int i=n; i>0; i--){
		ll r = findbest(pos[i]+1, pos[i]+k-1);
		ll l = findbest(pos[i]-k+1, pos[i]-1);
		if(r>n) jr[pos[i]][0] = pos[i];
		else jr[pos[i]][0] = pos[r];
		if(l>n) jl[pos[i]][0] = pos[i];
		else jl[pos[i]][0] = pos[l];
		best.upd(pos[i], pos[i], -1e15 + i);
	}
	for(auto y:h) cerr << y-1 << " "; cerr << endl;
	for(int i=0; i<n; i++) cerr << jr[i][0] << " "; cerr << endl;
	for(int i=0; i<n; i++) cerr << jl[i][0] << " "; cerr << endl;

	for(int k=1; k<20; k++){
		for(int i=0; i<n; i++){
			jl[i][k] = jl[jl[i][k-1]][k-1];
			jr[i][k] = jr[jr[i][k-1]][k-1];
		}
	}
}

int compare_plants(int x, int y) {
	// go from x to y right
	int xx = x;
	for(int i=19; i>=0; i--){
		if(jr[xx][i]<y and jr[xx][i]>x){
			xx=jr[xx][i];
		}
	}
	if(y<xx+K and h[xx]<h[y]){
		return -1;
	}
	int yy = y;
	for(int i=19; i>=0; i--){
		if(x < jl[yy][i] and jl[yy][i]<y){
			yy=jl[yy][i];
		}
	}
	if(yy - K < x and h[x] > h[yy]){
		return 1;
	}
	yy = y;
	for(int i=19; i>=0; i--){
		if(y < jr[yy][i] or jr[yy][i] < x){
			yy=jr[yy][i];
		}
	}
	if(x < yy + K and h[yy] < h[x]){
		return 1;
	}
	xx = x;
	for(int i=19; i>=0; i--){
		if(jl[xx][i]<x or y<jl[xx][i]){
			xx = jl[xx][i];
		}
	}
	if(xx-K < y and h[y]>h[xx]){
		return -1;
	}
	return 0;
}

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:146:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  146 |  for(auto y:h) cerr << y-1 << " "; cerr << endl;
      |  ^~~
plants.cpp:146:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  146 |  for(auto y:h) cerr << y-1 << " "; cerr << endl;
      |                                    ^~~~
plants.cpp:147:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  147 |  for(int i=0; i<n; i++) cerr << jr[i][0] << " "; cerr << endl;
      |  ^~~
plants.cpp:147:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  147 |  for(int i=0; i<n; i++) cerr << jr[i][0] << " "; cerr << endl;
      |                                                  ^~~~
plants.cpp:148:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  148 |  for(int i=0; i<n; i++) cerr << jl[i][0] << " "; cerr << endl;
      |  ^~~
plants.cpp:148:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  148 |  for(int i=0; i<n; i++) cerr << jl[i][0] << " "; cerr << endl;
      |                                                  ^~~~

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