Submission #7372

#	Time	Username	Problem	Language	Result	Execution time	Memory
7372		kriii	Dancing Elephants (IOI11_elephants)	C++98	100 / 100	5020 ms	23160 KiB

elephants

#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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3