Submission #1169858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169858		MateiKing80	Comparing Plants (IOI20_plants)	C++20	27 / 100	4014 ms	12080 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;
}

• 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