Submission #339409

#	Time	Username	Problem	Language	Result	Execution time	Memory
339409		oolimry	Comparing Plants (IOI20_plants)	C++14	44 / 100	768 ms	29932 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--;
}

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);
	}
	//for(int i = 0;i < n;i++) cout << H[i] << " ";
		
	return;
}

int compare_plants(int x, int y) {
	if(H[x] > H[y]) return 1;
	else return -1;
}

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:78:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   78 |  if(L < 0) L += n; if(R < 0) R += n;
      |  ^~
plants.cpp:78:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   78 |  if(L < 0) L += n; if(R < 0) R += n;
      |                    ^~

• 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