Submission #428930

#	Time	Username	Problem	Language	Result	Execution time	Memory
428930		alireza_kaviani	Comparing Plants (IOI20_plants)	C++11	14 / 100	105 ms	4240 KiB

plants

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

typedef pair<int, int> pii;

#define X		first
#define Y		second
#define lc		id << 1
#define rc		lc | 1

const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;

int n , k , ans = -1 , A[MAXN] , val[MAXN] , lz[MAXN << 2];
pii seg[MAXN << 2];
set<int> st;

void Insert(int x){
	int y = (*prev(st.lower_bound(x)));
	if(x - y >= k)	ans = x;
	st.insert(x);
}

void build(int id = 1 , int l = 0 , int r = n){
	if(r - l == 1){
		seg[id] = {A[l] , l};
		return;
	}
	int mid = l + r >> 1;
	build(lc , l , mid);
	build(rc , mid , r);
	seg[id] = min(seg[lc] , seg[rc]);
}

void shift(int id){
	lz[lc] += lz[id]; seg[lc].X += lz[id]; 
	lz[rc] += lz[id]; seg[rc].X += lz[id];
	lz[id] = 0;
}

void add(int ql , int qr , int val , int id = 1 , int l = 0 , int r = n){
	if(qr <= l || r <= ql)	return;
	if(ql <= l && r <= qr && (seg[id].X + val > 0 || r - l == 1)){
		lz[id] += val;
		seg[id].X += val;
		if(seg[id].X == 0)	Insert(l);
		return;
	}
	shift(id);
	int mid = l + r >> 1;
	add(ql , qr , val , lc , l , mid);
	add(ql , qr , val , rc , mid , r);
	seg[id] = min(seg[lc] , seg[rc]);
}

pii get(int ql , int qr , int id = 1 , int l = 0 , int r = n){
	if(qr <= l || r <= ql)	return {MOD , MOD};
	if(ql <= l && r <= qr)	return seg[id];
	shift(id);
	int mid = l + r >> 1;
	return min(get(ql , qr , lc , l , mid) , get(ql , qr , rc , mid , r));
}

void Add(int l , int r , int val){
	if(l < r){
		add(l , r , val);
		return;
	}
	add(0 , r , val); add(l , n , val);
	return;
}

pii Get(int l , int r){
	if(l < r)	return get(l , r);
	pii A = get(0 , r) , B = get(l , n);
	if(A.X < B.X)	return A;
	return B;
}

void init(int K, vector<int> r) {
	k = K; n = r.size();
	for(int i = 0 ; i < n ; i++)	A[i] = r[i];
	build(); st.insert(-1);
	for(int i = 0 ; i < n ; i++){
		if(A[i] == 0){
			Insert(i);
		}
	}
	for(int i = 0 ; i < n ; i++){
		int pos = ans;
		if(pos == -1)	pos = (*st.lower_bound(0));
		st.erase(pos);
		if(st.lower_bound(pos) != st.end()){
			ans = (*st.lower_bound(pos));
			if(ans < k - 1)	ans = -1;
		}
		else	ans = -1;
		Add((pos + n - k + 1) % n , pos , -1);
		Add(pos , pos + 1 , MOD);
		val[pos] = n - i;
	}
	return;
}

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

Compilation message (stderr)

plants.cpp: In function 'void build(int, int, int)':
plants.cpp:30:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int mid = l + r >> 1;
      |            ~~^~~
plants.cpp: In function 'void add(int, int, int, int, int, int)':
plants.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int mid = l + r >> 1;
      |            ~~^~~
plants.cpp: In function 'pii get(int, int, int, int, int)':
plants.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int mid = l + r >> 1;
      |            ~~^~~

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