oj.uz

Submission #13506

# Submission time Handle Problem Language Result Execution time Memory
13506 2015-02-22T05:04:04 Z ainta Dancing Elephants (IOI11_elephants) C++
100 / 100
 4353 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++){
		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.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
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 21708 KB Output is correct
2 Correct 447 ms 21708 KB Output is correct
3 Correct 543 ms 21708 KB Output is correct
4 Correct 464 ms 21708 KB Output is correct
5 Correct 452 ms 21708 KB Output is correct
6 Correct 792 ms 21708 KB Output is correct
7 Correct 447 ms 21708 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 21708 KB Output is correct
2 Correct 647 ms 21708 KB Output is correct
3 Correct 1336 ms 21708 KB Output is correct
4 Correct 1365 ms 21708 KB Output is correct
5 Correct 1459 ms 21708 KB Output is correct
6 Correct 865 ms 21708 KB Output is correct
7 Correct 1349 ms 21708 KB Output is correct
8 Correct 1297 ms 21708 KB Output is correct
9 Correct 756 ms 21708 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3532 ms 21708 KB Output is correct
2 Correct 3731 ms 21708 KB Output is correct
3 Correct 2881 ms 21708 KB Output is correct
4 Correct 3180 ms 21708 KB Output is correct
5 Correct 3218 ms 21708 KB Output is correct
6 Correct 2116 ms 21708 KB Output is correct
7 Correct 2036 ms 21708 KB Output is correct
8 Correct 2093 ms 21708 KB Output is correct
9 Correct 2058 ms 21708 KB Output is correct
10 Correct 2699 ms 21708 KB Output is correct
11 Correct 1966 ms 21708 KB Output is correct
12 Correct 2788 ms 21708 KB Output is correct
13 Correct 2065 ms 21708 KB Output is correct
14 Correct 1144 ms 21708 KB Output is correct
15 Correct 3397 ms 21708 KB Output is correct
16 Correct 2735 ms 21708 KB Output is correct
17 Correct 2836 ms 21708 KB Output is correct
18 Correct 2657 ms 21708 KB Output is correct
19 Correct 4239 ms 21708 KB Output is correct
20 Correct 4353 ms 21708 KB Output is correct