oj.uz

Submission #7384

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

const int maxGroup = 388;
const int maxSize = 388;

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 23184 KB Output is correct
2 Correct 0 ms 23184 KB Output is correct
3 Correct 0 ms 23184 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 23184 KB Output is correct
2 Correct 244 ms 23184 KB Output is correct
3 Correct 348 ms 23184 KB Output is correct
4 Correct 364 ms 23184 KB Output is correct
5 Correct 380 ms 23184 KB Output is correct
6 Correct 532 ms 23184 KB Output is correct
7 Correct 368 ms 23184 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 23184 KB Output is correct
2 Correct 392 ms 23184 KB Output is correct
3 Correct 840 ms 23184 KB Output is correct
4 Correct 896 ms 23184 KB Output is correct
5 Correct 956 ms 23184 KB Output is correct
6 Correct 788 ms 23184 KB Output is correct
7 Correct 900 ms 23184 KB Output is correct
8 Correct 860 ms 23184 KB Output is correct
9 Correct 592 ms 23184 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4256 ms 23184 KB Output is correct
2 Correct 4372 ms 23184 KB Output is correct
3 Correct 3936 ms 23184 KB Output is correct
4 Correct 4640 ms 23184 KB Output is correct
5 Correct 5364 ms 23184 KB Output is correct
6 Correct 1180 ms 23184 KB Output is correct
7 Correct 1124 ms 23184 KB Output is correct
8 Correct 1192 ms 23184 KB Output is correct
9 Correct 1124 ms 23184 KB Output is correct
10 Correct 3920 ms 23184 KB Output is correct
11 Correct 2576 ms 23184 KB Output is correct
12 Correct 4340 ms 23184 KB Output is correct
13 Correct 2848 ms 23184 KB Output is correct
14 Correct 1652 ms 23184 KB Output is correct
15 Correct 4384 ms 23184 KB Output is correct
16 Correct 4300 ms 23184 KB Output is correct
17 Correct 4920 ms 23184 KB Output is correct
18 Correct 4384 ms 23184 KB Output is correct
19 Correct 4852 ms 23184 KB Output is correct
20 Correct 4944 ms 23184 KB Output is correct