Submission #400306

#	Time	Username	Problem	Language	Result	Execution time	Memory
400306		faresbasbs	Comparing Plants (IOI20_plants)	C++14	0 / 100	65 ms	4840 KiB

plants

#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

struct node{
	int val,lazy;
};

int n,t,k,cnt,val[200001];
vector<node> segment;

void push(int curr){
	for(int i = 2*curr ; i <= 2*curr+1 ; i += 1){
		segment[i].lazy += segment[curr].lazy , segment[i].val += segment[curr].lazy;
	}
	segment[curr].lazy = 0;
}

void pull(int curr){
	segment[curr].val = min(segment[2*curr].val,segment[2*curr+1].val);
}

void upd(int a , int b , int v , int curr , int l , int r){
	if(b < l || a > r){
		return ;
	}
	if(a <= l && b >= r){
		segment[curr].val = v , segment[curr].lazy = 0;
		return ;
	}
	int mid = (l+r)/2;
	push(curr);
	upd(a,b,v,2*curr,l,mid),upd(a,b,v,2*curr+1,mid+1,r);
	pull(curr);
}

void rupd(int a , int b , int curr , int l , int r){
	if(b < l || a > r){
		return ;
	}
	if(a <= l && b >= r){
		segment[curr].lazy -= 1 , segment[curr].val -= 1;
		return ;
	}
	int mid = (l+r)/2;
	push(curr);
	rupd(a,b,2*curr,l,mid),rupd(a,b,2*curr+1,mid+1,r);
	pull(curr);
}

void u(int pos){
	val[pos] = cnt++;
	upd(pos,pos,1000000000,1,1,t);
	if(pos > 1){
		if(pos >= k){
			rupd(pos-k+1,pos-1,1,1,t);
		}else{
			int num = k-pos;
			rupd(1,pos-1,1,1,t),rupd(n-num,n,1,1,t);
		}
	}else{
		rupd(n-k+2,n,1,1,t);
	}
	// for(int i = 1 ; i < 2*t ; i += 1){
	// 	if(i < t){
	// 		push(i);
	// 	}
	// 	cout << segment[i].val << " ";
	// }cout << endl;
}

int fnd2(int a , int b , int curr , int l , int r){
	if(b < l || a > r){
		return -1;
	}
	if(a <= l && b >= r){
		// cout << cnt << " " << curr << " " << segment[curr].val << endl;
		if(segment[curr].val != 0){
			return -1;
		}
		while(curr < t){
			push(curr);
			if(segment[2*curr].val == 0){
				curr = 2*curr;
			}else{
				curr = 2*curr+1;
			}
		}
		return curr-t+1;
	}
	int mid = (l+r)/2;
	push(curr);
	int f = fnd2(a,b,2*curr,l,mid);
	if(f != -1){
		return f;
	}
	return fnd2(a,b,2*curr+1,mid+1,r);
}

int fnd(){
	int pos = fnd2(1,n,1,1,t);
	if(pos > 1){
		if(pos >= k){
			int f = fnd2(pos-k+1,pos-1,1,1,t);
			if(f != -1){
				return f;
			}
		}else{
			int num = k-pos;
			int f = fnd2(n-num,n,1,1,t);
			if(f != -1){
				return f;
			}
			f = fnd2(1,pos-1,1,1,t);
			if(f != -1){
				return f;
			}
		}
	}else{
		int f = fnd2(n-k+2,n,1,1,t);
		if(f != -1){
			return f;
		}
	}
	return pos;
}

void init(int K , vector<int> r){
	n = r.size() , cnt = 0 , k = K;
	t = pow(2,ceil(log2(n)));
	segment.resize(2*t,{0,0});
	for(int i = 0 ; i < (int)r.size() ; i += 1){
		upd(i+1,i+1,r[i],1,1,t);
	}
	for(int i = 0 ; i < n ; i += 1){
		int f = fnd();
		u(f);
	}
}

int compare_plants(int x, int y){
	if(val[x+1] < val[y+1]){
		return 1;
	}
	return -1;
}

• 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