Submission #269170

#	Time	Username	Problem	Language	Result	Execution time	Memory
269170		Plurm	Dancing Elephants (IOI11_elephants)	C++11	50 / 100	9095 ms	1784 KiB

elephants

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

int n, l;
int arr[150005];
int pos[150005];
void init(int N, int L, int X[])
{
	n = N;
	l = L;
	for(int i = 0; i < N; i++){
		arr[i] = X[i];
		pos[i] = X[i];
	}
}

int update(int i, int y)
{
	int idx = lower_bound(arr, arr+n, pos[i]) - arr;
	for(int j = idx; j < n; j++) arr[j] = arr[j+1];
	pos[i] = y;
	idx = lower_bound(arr, arr+n-1, pos[i]) - arr;
	for(int j = n-1; j > idx; j--) arr[j] = arr[j-1];
	arr[idx] = pos[i];
	int last = -1;
	int c = 0;
	for(int j = 0; j < n; j++){
		if(last < arr[j]){
			last = arr[j]+l;
			if(arr[j+20] < last){
				j = upper_bound(arr, arr+n, last) - arr;
				j--;
			}
			c++;
		}
	}
	return c;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3