제출 #227470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
227470		spdskatr	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	7245 ms	14944 KiB

elephants

// This problem is cooked
#include "elephants.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cassert>
#define fi first
#define se second
#define K 404 // Not found

using namespace std;
typedef pair<int, int> pii;
int N, L, cnt, loc[150005], curblock[150005];
pair<int, int> el[150005];

struct block {
	int val[K<<1], pos[K<<1], dp[K<<1], ext[K<<1], sz;
	void reset() {
		fill(val, val+K, 0);
		fill(dp, dp+K, 0);
	}
	void recalc() {
		int rp = sz;
		for (int i = sz - 1; i >= 0; i--) {
			while (pos[rp-1] > pos[i] + L) rp--;
			if (rp == sz) {
				dp[i] = 1;
				ext[i] = pos[i] + L + 1;
			} else {
				dp[i] = dp[rp] + 1;
				ext[i] = ext[rp];
			}
		}
	}
	void remove(int x) {
		int lp = 0;
		while (val[lp] != x && lp < sz) lp++;
		assert(val[lp] == x);
		sz--;
		while (lp < sz) {
			val[lp] = val[lp+1];
			pos[lp] = pos[lp+1];
			lp++;
		}
		val[sz] = pos[sz] = 0;
		recalc();
	}
	void insert(int x, int v) {
		int lp = 0;
		while (lp < sz && pos[lp] < v) lp++;
		sz++;
		for (int i = sz-1; i > lp; i--) {
			val[i] = val[i-1];
			pos[i] = pos[i-1];
		}
		val[lp] = x, pos[lp] = v;
		recalc();
	}
} sd[505];

void init(int n, int l, int X[])
{
	N = n, L = l;
	for (int i = 0; i < N; i++) loc[i] = X[i];
	for (int b = 0; b * K < N; b++) {
		for (int j = 0; j < min(K, N-b*K); j++) {
			int actual = b*K+j;
			sd[b].val[j] = actual;
			sd[b].pos[j] = loc[actual];
			curblock[actual] = b;
		}
		sd[b].sz = min(K, N-b*K);
		sd[b].recalc();
	}
}

int update(int ind, int y)
{
	loc[ind] = y;
	if (cnt >= K - 1) {
		// Recalculate everything
		for (int i = 0; i < N; i++) el[i] = { loc[i], i };
		sort(el, el+N);
		for (int b = 0; b*K < N; b++) {
			sd[b].reset();
			for (int j = 0; j < min(K, N-b*K); j++) {
				int actual = b*K + j;
				sd[b].val[j] = el[actual].se;
				sd[b].pos[j] = el[actual].fi;
				curblock[el[actual].se] = b;
			}
			sd[b].sz = min(K, N-b*K);
			sd[b].recalc();
		}
		cnt = 0;
	} else {
		int b2 = 0;
		sd[curblock[ind]].remove(ind);
		while ((b2 + 1) * K < N && sd[b2+1].sz > 0 && sd[b2+1].pos[0] < loc[ind]) {
			b2++;
		}
		curblock[ind] = b2;
		sd[b2].insert(ind, loc[ind]);
	}
	int curpt = 0, tot = 0;
	for (int b = 0; (b+1)*K < N || (b*K < N && sd[b].sz > 0); b++) {
		if (sd[b].pos[sd[b].sz-1] >= curpt) {
			int lo = 0, hi = sd[b].sz;
			if (sd[b].pos[0] >= curpt) hi = 0;
			else while (lo + 1 < hi) {
				int mid = (lo + hi) / 2;
				if (sd[b].pos[mid] < curpt) lo = mid;
				else hi = mid;
			}
			tot += sd[b].dp[hi];
			curpt = sd[b].ext[hi];
			assert(curpt > sd[b].pos[sd[b].sz-1]);
		}
	}
	cnt++;
	return tot;
}

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