Submission #339737

#	Time	Username	Problem	Language	Result	Execution time	Memory
339737		oolimry	Comparing Plants (IOI20_plants)	C++14	0 / 100	1 ms	512 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--;
}

int L[200005];
int R[200005];
int mat[305][305];

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));
	}
		
	for(int i = 0;i < n;i++){
		auto it = Left.upper_bound(ii(H[i],0));
		if(it != Left.begin()){
			it--;
			L[i] = it->second;
		}
		else L[i] = -1;
		
		it = Right.upper_bound(ii(H[i],0));
		if(it != Right.begin()){
			it--;
			R[i] = it->second;
		}
		else R[i] = -1;
		
		Left.erase(get(i-K+1));
		Left.insert(get(i));
		Right.erase(get(i+1));
		Right.erase(get(i+K));
	}
	
	for(int i = 0;i < n;i++){
		mat[i][L[i]] = 1;
		mat[i][R[i]] = 1;
	}
	
	for(int k = 0;k < n;k++) for(int i = 0;i < n;i++) for(int j = 0;j < n;j++){
		mat[i][j] = mat[i][j] | (mat[i][k] & mat[k][j]);
	}
		
	return;
}

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

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: 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