Submission #105401

#	Time	Username	Problem	Language	Result	Execution time	Memory
105401		eriksuenderhauf	Dancing Elephants (IOI11_elephants)	C++11	100 / 100	2931 ms	21708 KiB

elephants

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "elephants.h"
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int ll;
const int INF = 1e9 + 7;
const int MAXN = 15e4 + 5;
const int BLOCK = 513;
int n, l, a[MAXN], b[MAXN], st[BLOCK];
int bcnt = 1, buc[BLOCK][2 * BLOCK + 1];
int val[BLOCK][2 * BLOCK + 1][2];
map<int,int> cnt;

void calc(int ind) {
	int sz = buc[ind][0];
	for (int i = sz; i > 0; i--) {
		while (sz > 0 && buc[ind][i] + l < buc[ind][sz]) 
			sz--;
		if (sz < buc[ind][0]) {
			val[ind][i][0] = val[ind][sz + 1][0] + 1;
			val[ind][i][1] = val[ind][sz + 1][1];
		} else {
			val[ind][i][0] = 1;
			val[ind][i][1] = buc[ind][i];
		}
	}
}

void build() {
	bcnt = 0;
	for (int i = 0; i * BLOCK < n; i++) {
		bcnt++;
		buc[i][0] = 0;
		for (int j = 0; j < BLOCK && BLOCK * i + j < n; j++)
			buc[i][++buc[i][0]] = b[BLOCK * i + j];
		calc(i);
		st[i] = buc[i][1];
	}
}

void init(int N, int L, int X[]) {
	n = N, l = L;
	for (int i = 0; i < n; i++) {
		a[i] = X[i], b[i] = X[i];
		cnt[X[i]]++;
	}
	n = unique(b, b + n) - b;
	build();
}

void restore() {
	int cur = 0;
	for (int i = 0; i < bcnt; i++)
		for (int j = 1; j <= buc[i][0]; j++)
			b[cur++] = buc[i][j];
}

int getBucket(int pos) {
	return lower_bound(st + 1, st + bcnt, pos + 1) - st - 1;
}

int update(int ind, int pos) {
	cnt[a[ind]]--;
	if (cnt[a[ind]] == 0) {
		int b = getBucket(a[ind]);
		int s = lower_bound(buc[b] + 1, buc[b] + buc[b][0] + 1, a[ind]) - buc[b];
		for (int i = s; i < buc[b][0]; i++)
			buc[b][i] = buc[b][i + 1];
		n--, buc[b][0]--;
		calc(b);
	}
	cnt[pos]++;
	if (cnt[pos] == 1) {
		int b = getBucket(pos);
		if (buc[b][0] == 2 * BLOCK) {
			restore();
			build();
			b = getBucket(pos);
		}
		int s = lower_bound(buc[b] + 1, buc[b] + buc[b][0] + 1, pos) - buc[b];
		for (int i = buc[b][0] + 1; i > s; i--)
			buc[b][i] = buc[b][i - 1];
		buc[b][s] = pos;
		n++, buc[b][0]++;
		calc(b);
	}
	a[ind] = pos;
	int ret = 0, cur = -INF;
	for (int i = 0; i < bcnt; i++) {
		int nx = lower_bound(buc[i] + 1, buc[i] + buc[i][0] + 1, cur + l + 1) - buc[i];
		if (nx > buc[i][0]) continue; // picture ends in the next bucket
		ret += val[i][nx][0];
		cur = val[i][nx][1];
	}
	return ret;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3