Submission #1215340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215340		JooDdae	Dancing Elephants (IOI11_elephants)	C++20	100 / 100	2198 ms	7532 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int sq = 400;

int X[150015], L;

struct group {
	int x[808], p[808], r[808], sz;

	void update() {
		for(int i=sz-1, j=sz;i>=0;i--) {
			while(j > i && x[j-1]-x[i] > L) j--;
			if(j == sz) r[i] = x[i], p[i] = 1;
			else r[i] = r[j], p[i] = p[j]+1;
		}
	}

	void add(int u) {
		x[sz++] = u;
		for(int i=sz-1;i>0;i--) if(x[i] < x[i-1]) swap(x[i], x[i-1]);
		update();
	}

	void erase(int u) {
		int k = 0;
		while(x[k] != u) k++;
		for(int i=k+1;i<sz;i++) swap(x[i-1], x[i]);
		sz--;
		update();
	}
} g[404];

int N, cnt, P[150015];

void rebuild() {
	int c = 0;
	for(int i=0;i<sq;i++) for(int j=0;j<g[i].sz;j++) P[c++] = g[i].x[j];
	for(int i=0;i<=(N-1)/sq;i++) g[i].sz = 0;
	for(int i=0;i<N;i++) g[i/sq].x[g[i/sq].sz++] = P[i];
	for(int i=0;i<=(N-1)/sq;i++) g[i].update();
}

void init(int N, int L, int X[]) {
	::L = L, ::N = N;
	memcpy(::X, X, sizeof(int)*N), memcpy(P, X, sizeof(int)*N);
	rebuild();
}

int get_group(int x) {
	int re = sq-1;
	while(re && (!g[re].sz || x < g[re].x[0])) re--;
	return re;
}

int update(int i, int y) {
	g[get_group(X[i])].erase(X[i]);
	X[i] = y, g[get_group(y)].add(y);

	if(++cnt == sq) rebuild(), cnt = 0;

	int ans = 0, R = -1;
	for(int i=0;i<sq;i++) if(g[i].sz && R < g[i].x[g[i].sz-1]) {
		int s = 0, e = g[i].sz-1;
		while(s <= e) {
			int mid = (s+e) >> 1;
			if(g[i].x[mid] <= R) s = mid+1;
			else e = mid-1;
		}
		ans += g[i].p[s], R = g[i].r[s]+L;
	}

	return ans;
}

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