Submission #1215339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215339		JooDdae	Dancing Elephants (IOI11_elephants)	C++20	50 / 100	9093 ms	5260 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, in[150015];

void rebuild() {
	vector<array<int, 2>> p(N);
	for(int i=0;i<N;i++) p[i] = {X[i], i};
	sort(p.begin(), p.end());
	for(int i=0;i<sq;i++) g[i].sz = 0;
	for(int i=0;i<N;i++) in[p[i][1]] = i/sq, g[i/sq].add(p[i][0]);
}

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

int update(int i, int y) {
	g[in[i]].erase(X[i]);
	
	X[i] = y, in[i] = sq-1;
	while(in[i] && (!g[in[i]].sz || y < g[in[i]].x[0])) in[i]--;
	g[in[i]].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: 0 / 47
• Subtask 5: 0 / 3