oj.uz

Submission #7372

# Submission time Handle Problem Language Result Execution time Memory
7372 2014-08-04T10:31:57 Z kriii Dancing Elephants (IOI11_elephants) C++
100 / 100
 5020 ms 23160 KB 
#include "elephants.h"
#include <algorithm>
using namespace std;

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

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 204 ms 23160 KB Output is correct
2 Correct 220 ms 23160 KB Output is correct
3 Correct 336 ms 23160 KB Output is correct
4 Correct 360 ms 23160 KB Output is correct
5 Correct 332 ms 23160 KB Output is correct
6 Correct 488 ms 23160 KB Output is correct
7 Correct 364 ms 23160 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 23160 KB Output is correct
2 Correct 360 ms 23160 KB Output is correct
3 Correct 760 ms 23160 KB Output is correct
4 Correct 856 ms 23160 KB Output is correct
5 Correct 876 ms 23160 KB Output is correct
6 Correct 984 ms 23160 KB Output is correct
7 Correct 852 ms 23160 KB Output is correct
8 Correct 800 ms 23160 KB Output is correct
9 Correct 632 ms 23160 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4352 ms 23160 KB Output is correct
2 Correct 4328 ms 23160 KB Output is correct
3 Correct 4044 ms 23160 KB Output is correct
4 Correct 4996 ms 23160 KB Output is correct
5 Correct 5020 ms 23160 KB Output is correct
6 Correct 988 ms 23160 KB Output is correct
7 Correct 924 ms 23160 KB Output is correct
8 Correct 1012 ms 23160 KB Output is correct
9 Correct 920 ms 23160 KB Output is correct
10 Correct 3832 ms 23160 KB Output is correct
11 Correct 2864 ms 23160 KB Output is correct
12 Correct 4548 ms 23160 KB Output is correct
13 Correct 3024 ms 23160 KB Output is correct
14 Correct 1800 ms 23160 KB Output is correct
15 Correct 4168 ms 23160 KB Output is correct
16 Correct 4308 ms 23160 KB Output is correct
17 Correct 4580 ms 23160 KB Output is correct
18 Correct 4212 ms 23160 KB Output is correct
19 Correct 4624 ms 23160 KB Output is correct
20 Correct 4724 ms 23160 KB Output is correct