Submission #43762

#	Time	Username	Problem	Language	Result	Execution time	Memory
43762		baactree	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	4352 ms	83804 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
int n, l;
struct group {
	int sz;
	int arr[1005],cnt[1005],last[1005];
	group() :sz(0){}
	void improve() {
		for (int i = sz - 1, k = sz - 1; i >= 0; i--) {
			if (arr[i] + l >= arr[k]) {
				cnt[i] = 1;
				last[i] = arr[i] + l;
			}
			else {
				while (arr[i] + l < arr[k-1])k--;
				cnt[i] = cnt[k] + 1;
				last[i] = last[k];
			}
		}
	}
};
int x[150005],t[150005];
int cnt, sz;
group g[505];
int gg;
void init(int N, int L, int X[]){
	n = N; l = L;
	for (int i = 0; i < n; i++) 
		x[i] = X[i];
	cnt = 0;
	sz = sqrt(n) + 1;
	gg = (n + sz - 1) / sz;
	for (int i = 0; i < n; i++)
		g[i / sz + 1].arr[g[i / sz + 1].sz++] = x[i];
}
void calc() {
	int idx = 0;
	for (int i = 1; i <= gg; i++) {
		for (int j = 0; j < g[i].sz; j++) 
			t[idx++] = g[i].arr[j];
		g[i].sz = 0;
	}
	gg = (idx + sz - 1) / sz;
	for (int i = 0; i < idx; i++) 
		g[i / sz + 1].arr[g[i / sz + 1].sz++] = t[i];
	for (int i = 1; i <= gg; i++)
		g[i].improve();
}
void erase(int now) {
	int ng;
	for (ng = gg; ng > 1; ng--)
		if (g[ng].arr[0] <= now)break;
	int idx;
	for (idx = 0; idx < g[ng].sz; idx++)
		if (g[ng].arr[idx] == now)break;
	g[ng].sz--;
	for (int i = idx; i < g[ng].sz; i++)
		g[ng].arr[i] = g[ng].arr[i + 1];
	if (!g[ng].sz)calc();
	else g[ng].improve();
}
void insert(int now) {
	int ng;
	for (ng = gg; ng > 1; ng--)
		if (g[ng].arr[0] <= now)break;
	int idx;
	for (idx = 0; idx < g[ng].sz; idx++)
		if (now < g[ng].arr[idx])break;
	for (int i = g[ng].sz; i > idx; i--)
		g[ng].arr[i] = g[ng].arr[i - 1];
	g[ng].sz++;
	g[ng].arr[idx] = now;
	g[ng].improve();
}
int get_ans() {
	int ret = 0;
	int last = -1;
	for (int i = 1; i <= gg; i++) {
		int le, ri, mid, idx;
		le = 0;
		ri = g[i].sz - 1;
		idx = -1;
		while (le <= ri) {
			mid = (le + ri) / 2;
			if (last < g[i].arr[mid]) {
				idx = mid;
				ri = mid - 1;
			}
			else
				le = mid + 1;
		}
		if (idx == -1)continue;
		last = g[i].last[idx];
		ret += g[i].cnt[idx];
	}
	return ret;
}
int update(int i, int y){
	if (cnt%sz == 0)calc();
	erase(x[i]);
	insert(x[i]=y);
	cnt++;
	return get_ans();
}

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