Submission #339746

#	Time	Username	Problem	Language	Result	Execution time	Memory
339746		oolimry	Comparing Plants (IOI20_plants)	C++14	30 / 100	2416 ms	98632 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) x.size();
using namespace std;
typedef pair<int,int> ii;

struct node{
	int s, e, m;
	ii val = ii(0,0); int lazy = 0;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s == e) val = ii(0, S);
		else{
			l = new node(s, m);
			r = new node(m+1, e);
			val = min(l->val, r->val);
		}
	}
	
	void apply(int L){
		val.first += L;
		lazy += L;
	}
	void push(){
		if(s == e) return;
		l->apply(lazy);
		r->apply(lazy);
		lazy = 0;
	}
	
	void update(int S, int E, int L){
		push();
		if(s == S && E == e){
			apply(L);
			return;
		}
		else if(E <= m) l->update(S, E, L);
		else if(S >= m+1) r->update(S, E, L);
		else l->update(S, m, L), r->update(m+1, E, L);
		val = min(l->val, r->val);
	}
	
	ii query(int S, int E){
		push();
		if(s == S && E == e) return val;
		else if(E <= m) return l->query(S, E);
		else if(S >= m+1) return r->query(S, E);
		else return min(l->query(S, m), r->query(m+1, E));
	}
} *root;


int n, K;
int H[200005];
int height;

void assign(int u){
	while(true){
		int R = u-1, L = u-K+1;
		if(L < 0) L += n; if(R < 0) R += n;
		
		ii res;
		if(L <= R) res = root->query(L,R);
		else res = min(root->query(L, n-1), root->query(0,R));
		
		if(res.first == 0) assign(res.second);
		else break;
	}
	
	H[u] = height;
	int R = u-1, L = u-K+1;
	if(L < 0) L += n; if(R < 0) R += n;
	
	if(L <= R) root->update(L, R, -1);
	else root->update(L, n-1, -1), root->update(0, R, -1);
	
	root->update(u, u, 1e9);
	height--;
}

ii pl[20][200005];
ii pr[20][200005];

ii get(int i){
	if(i < 0) i += n;
	if(i >= n) i -= n;
	return ii(H[i], i);
}

void init(int _K, vector<int> R) {
	n = sz(R); K = _K;
	
	root = new node(0, n-1);
	for(int i = 0;i < n;i++) root->update(i,i,R[i]);
	
	fill(H,H+n,-1);
	height = n-1;
	while(height >= 0){
		ii res = root->query(0, n-1);
		assign(res.second);
	}
	
	set<ii> Left, Right;
	
	for(int k = 1;k < K;k++){
		Left.insert(get(-k));
		Right.insert(get(k));
	}
	
	H[n] = -1; ///dummy height
		
	for(int i = 0;i < n;i++){
		auto it = Left.upper_bound(ii(H[i],0));
		if(it != Left.begin()){
			it--;
			int dis = i - it->second;
			if(dis < 0) dis += n;
			pl[0][i] = ii(it->second, dis);
		}
		else pl[0][i] = ii(n, -1);
		
		it = Right.upper_bound(ii(H[i],0));
		if(it != Right.begin()){
			it--;
			int dis = it->second - i;
			if(dis < 0) dis += n;
			pr[0][i] = ii(it->second, dis);
		}
		else pr[0][i] = ii(n, -1);
		
		Left.erase(get(i-K+1));
		Left.insert(get(i));
		Right.erase(get(i+1));
		Right.insert(get(i+K));
	}
	
	for(int k = 0;k <= 18;k++) pl[k][n] = ii(n, -1), pr[k][n] = ii(n, -1); ///dummy
	for(int k = 1;k <= 18;k++){
		for(int i = 0;i < n;i++){
			ii a = pl[k-1][i];
			ii b = pl[k-1][a.first];
			pl[k][i] = ii(b.first, a.second+b.second);
			
			a = pr[k-1][i];
			b = pr[k-1][a.first];
			pr[k][i] = ii(b.first, a.second+b.second);
		}
	}
	
	return;
}

int compare_plants(int x, int y) {
	int ans = 1;
	
	if(H[x] < H[y]){
		swap(x, y);
		ans *= -1;
	}
	
	long long dL = 0, dR = 0;
	
	int u = x;
	for(int k = 18;k >= 0;k--){
		ii toL = pl[k][u];
		if(H[toL.first] > H[y]){
			dL += toL.second;
			u = toL.first;
		}
	}
	
	u = x;
	for(int k = 18;k >= 0;k--){
		ii toR = pr[k][u];
		if(H[toR.first] > H[y]){
			dR += toR.second;
			u = toR.first;
		}
	}
	
	int needL = x - y;
	if(needL < 0) needL += n;
	needL -= (K-1);
	
	int needR = y - x;
	if(needR < 0) needR += n;
	needR -= (K-1);
	
	if(dL < needL && dR < needR) ans = 0;	
	return ans;
}

Compilation message (stderr)

plants.cpp: In function 'void assign(int)':
plants.cpp:63:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   63 |   if(L < 0) L += n; if(R < 0) R += n;
      |   ^~
plants.cpp:63:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   63 |   if(L < 0) L += n; if(R < 0) R += n;
      |                     ^~
plants.cpp:75:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   75 |  if(L < 0) L += n; if(R < 0) R += n;
      |  ^~
plants.cpp:75:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   75 |  if(L < 0) L += n; if(R < 0) R += n;
      |                    ^~

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