Submission #13506

#	Time	Username	Problem	Language	Result	Execution time	Memory
13506		ainta	Dancing Elephants (IOI11_elephants)	C++98	100 / 100	4353 ms	21708 KiB

elephants

#include "elephants.h"

int n, w[151000], D, C[310], SZ, CC, Tw[151000];
struct BList{
	int x, d, pv;
}P[310][1050];

void UDT(int a){
	int i, pv = C[a] + 1;
	for (i = C[a]; i >= 1; i--){
		while (P[a][pv - 1].x - P[a][i].x > D)pv--;
		if (pv == C[a] + 1)P[a][i].d = 0, P[a][i].pv = i;
		else P[a][i].d = P[a][pv].d + 1, P[a][i].pv = P[a][pv].pv;
	}
}

void init(int N, int L, int X[])
{
	int i;
	n = N, D = L;
	for (i = 0; i < N; i++){
		w[i] = X[i];
		C[i >> 9]++;
		P[i >> 9][C[i >> 9]].x = w[i];
	}
	SZ = (N - 1) >> 9;
	for (i = 0; i <= SZ; i++)UDT(i);
}

void init2(){
	int i, j, cnt = 0;
	for (i = 0; i <= SZ; i++){
		for (j = 1; j <= C[i]; j++)Tw[cnt++] = P[i][j].x;
		C[i] = 0;
	}
	for (i = 0; i < n; i++){
		C[i >> 9]++;
		P[i >> 9][C[i >> 9]].x = Tw[i];
	}
	for (i = 0; i <= SZ; i++)UDT(i);
}
int Find(int be, int x){
	int i, j, b, e, mid, r;
	for (i = be; i <= SZ; i++){
		if (C[i] && P[i][C[i]].x >= x)break;
	}
	if (i == SZ + 1)return (SZ << 10) + C[SZ] + 1;
	b = 1, e = C[i];
	while (b <= e){
		mid = (b + e) >> 1;
		if (P[i][mid].x >= x)r = mid, e = mid - 1;
		else b = mid + 1;
	}
	return (i << 10) + r;
}

void Del(int x){
	int a = Find(0, x), b, i;
	b = a & 1023; a >>= 10;
	for (i = b; i < C[a]; i++)P[a][i].x = P[a][i + 1].x;
	C[a]--;
	UDT(a);
}
void Add(int x){
	int a = Find(0, x), b, i;
	b = a & 1023; a >>= 10;
	for (i = C[a]; i >= b; i--)P[a][i + 1].x = P[a][i].x;
	P[a][b].x = x;
	C[a]++;
	UDT(a);
}

int update(int i, int y)
{
	CC++;
	if (CC % 500 == 0){
		init2();
	}
	Del(w[i]);
	w[i] = y;
	Add(w[i]);
	int a, b, r = 0;
	for (i = 0; i <= SZ; i++)if (C[i])break;
	a = i, b = 1;
	while (1){
		if (a == SZ && b == C[SZ] + 1)break;
		r += P[a][b].d;
		b = P[a][b].pv;
		r++;
		a = Find(a + 1, P[a][b].x + D + 1);
		b = a & 1023; a >>= 10;
	}
	return r;
}

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