Submission #428892

#	Time	Username	Problem	Language	Result	Execution time	Memory
428892		alireza_kaviani	Comparing Plants (IOI20_plants)	C++11	27 / 100	4067 ms	11972 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 , A[MAXN] , val[MAXN] , lz[MAXN << 2];
pii seg[MAXN << 2];

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){
		lz[id] += val;
		seg[id].X += val;
		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();	
	for(int i = 0 ; i < n ; i++){
		int pos = Get(0 , n).Y;
		while(1){
			pii A = Get((pos + n - k + 1) % n , pos);
			if(A.X == 0)	pos = A.Y;
			else	break;
		}
		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:23:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |  int mid = l + r >> 1;
      |            ~~^~~
plants.cpp: In function 'void add(int, int, int, int, int, int)':
plants.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |  int mid = l + r >> 1;
      |            ~~^~~
plants.cpp: In function 'pii get(int, int, int, int, int)':
plants.cpp:53:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int mid = l + r >> 1;
      |            ~~^~~

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