oj.uz

Submission #13505

# Submission time Handle Problem Language Result Execution time Memory
13505 2015-02-22T05:02:50 Z ainta Dancing Elephants (IOI11_elephants) C++
26 / 100
 130 ms 21708 KB 
#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++){
		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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21708 KB Output is correct
2 Correct 0 ms 21708 KB Output is correct
3 Correct 0 ms 21708 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21708 KB Output is correct
2 Correct 0 ms 21708 KB Output is correct
3 Correct 0 ms 21708 KB Output is correct

Subtask #3
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 21704 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 21704 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 130 ms 21704 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -