oj.uz

Submission #7385

# Submission time Handle Problem Language Result Execution time Memory
7385 2014-08-05T00:59:40 Z kriii Dancing Elephants (IOI11_elephants) C++
100 / 100
 5000 ms 23160 KB 
#include "elephants.h"
#include <algorithm>
using namespace std;

const int maxGroup = 300;
const int maxSize = 500;

int gcnt,wgroup[maxGroup*maxSize];
int size[maxGroup],start[maxGroup],index[maxGroup][maxSize*2],pos[maxGroup][maxSize*2],cnt[maxGroup][maxSize*2],npos[maxGroup][maxSize*2];

int l;

void makejump(int g)
{
	int s = size[g], *p = pos[g], *c = cnt[g], *n = npos[g];
	n[s] = -1; c[s] = 0;
	for (int i=s-1,j=s-1;i>=0;i--){
		while (p[i] + l < p[j]) j--; j++;
		n[i] = (n[j] == -1) ? p[i] + l : n[j];
		c[i] = c[j] + 1; j--;
	}
}

void init(int N, int L, int X[])
{
	l = L;
	for (int i=0;i<N;i++){
		int gp = i / maxSize;
		wgroup[i] = gp;
		index[gp][size[gp]] = i;
		pos[gp][size[gp]++] = X[i];
		gcnt = gp + 1;
	}

	for (int g=0;g<gcnt;g++){
		start[g] = pos[g][0];
		makejump(g);
	}
}

int indtemp[maxGroup*maxSize],postemp[maxGroup*maxSize];

void justify()
{
	int c = 0;
	for (int i=0;i<gcnt;i++){
		int *ind = index[i], *p = pos[i];
		for (int j=0;j<size[i];j++){
			indtemp[c] = ind[j];
			postemp[c] = p[j];
			c++;
		}
		size[i] = 0;
	}

	for (int i=0;i<c;i++){
		int gp = i / maxSize;
		wgroup[indtemp[i]] = gp;
		index[gp][size[gp]] = indtemp[i];
		pos[gp][size[gp]++] = postemp[i];
		gcnt = gp + 1;
	}

	for (int g=0;g<gcnt;g++){
		start[g] = pos[g][0];
		makejump(g);
	}
}

int update(int ind, int y)
{
	int g = wgroup[ind];
	for (int i=0;i<size[g];i++) if (index[g][i] == ind){
		for (int j=i+1;j<size[g];j++){
			index[g][j-1] = index[g][j];
			pos[g][j-1] = pos[g][j];
		}
		start[g] = pos[g][0];
		size[g]--;
		break;
	}
	if (size[g] == 0) justify();
	else makejump(g);

	g = lower_bound(start,start+gcnt,y) - start - 1;
	if (g < 0) g++;

	int i = lower_bound(pos[g],pos[g]+size[g],y) - pos[g];
	for (int j=size[g];j>i;j--){
		index[g][j] = index[g][j-1];
		pos[g][j] = pos[g][j-1];
	}
	wgroup[ind] = g;
	index[g][i] = ind;
	pos[g][i] = y;
	start[g] = pos[g][0];
	size[g]++;

	if (size[g] == maxSize * 2) justify();
	else makejump(g);

	int last = -1, k = 0;
	for (int i=0;i<gcnt;i++){
		if (pos[i][size[i]-1] <= last) continue;
		int u = upper_bound(pos[i],pos[i]+size[i],last) - pos[i];
		last = npos[i][u];
		k += cnt[i][u];
	}

	return k;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 23160 KB Output is correct
2 Correct 284 ms 23160 KB Output is correct
3 Correct 356 ms 23160 KB Output is correct
4 Correct 384 ms 23160 KB Output is correct
5 Correct 352 ms 23160 KB Output is correct
6 Correct 612 ms 23160 KB Output is correct
7 Correct 368 ms 23160 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 23160 KB Output is correct
2 Correct 448 ms 23160 KB Output is correct
3 Correct 976 ms 23160 KB Output is correct
4 Correct 996 ms 23160 KB Output is correct
5 Correct 1060 ms 23160 KB Output is correct
6 Correct 696 ms 23160 KB Output is correct
7 Correct 988 ms 23160 KB Output is correct
8 Correct 948 ms 23160 KB Output is correct
9 Correct 624 ms 23160 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4432 ms 23160 KB Output is correct
2 Correct 4412 ms 23160 KB Output is correct
3 Correct 4276 ms 23160 KB Output is correct
4 Correct 4696 ms 23160 KB Output is correct
5 Correct 4660 ms 23160 KB Output is correct
6 Correct 1488 ms 23160 KB Output is correct
7 Correct 1380 ms 23160 KB Output is correct
8 Correct 1460 ms 23160 KB Output is correct
9 Correct 1372 ms 23160 KB Output is correct
10 Correct 3544 ms 23160 KB Output is correct
11 Correct 2576 ms 23160 KB Output is correct
12 Correct 4208 ms 23160 KB Output is correct
13 Correct 2752 ms 23160 KB Output is correct
14 Correct 1612 ms 23160 KB Output is correct
15 Correct 4332 ms 23160 KB Output is correct
16 Correct 4116 ms 23160 KB Output is correct
17 Correct 4452 ms 23160 KB Output is correct
18 Correct 4172 ms 23160 KB Output is correct
19 Correct 4964 ms 23160 KB Output is correct
20 Correct 5000 ms 23160 KB Output is correct