Submission #761019

#	Time	Username	Problem	Language	Result	Execution time	Memory
761019		SanguineChameleon	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	9072 ms	19476 KiB

elephants

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

const int maxN = 1.5e5 + 20;
const int block_size = 400;
vector<int> pos[maxN];
vector<pair<int, int>> dp[maxN];
int A[maxN];
int N, L;
int block_cnt;

void calc_block(int id) {
	vector<int> &pos_block = pos[id];
	vector<pair<int, int>> &dp_block = dp[id];
	int sz = pos_block.size();
	dp_block.resize(sz);
	int rt = sz;
	for (int i = sz - 1; i >= 0; i--) {
		while (pos_block[rt - 1] > pos_block[i] + L) {
			rt--;
		}
		if (rt == sz) {
			dp_block[i].first = 1;
			dp_block[i].second = pos_block[i];
		}
		else {
			dp_block[i].first = dp_block[rt].first + 1;
			dp_block[i].second = dp_block[rt].second;
		}
	}
}

int calc_all() {
	int res = dp[0][0].first;
	int last = dp[0][0].second;
	for (int id = 1; id < block_cnt; id++) {
		if (pos[id].back() > last + L) {
			int i = upper_bound(pos[id].begin(), pos[id].end(), last + L) - pos[id].begin();
			res += dp[id][i].first;
			last = dp[id][i].second;
		}
	}
	return res;
}

void rem(int X) {
	int id = 0;
	while (pos[id].back() < X) {
		id++;
	}
	pos[id].erase(lower_bound(pos[id].begin(), pos[id].end(), X));
	if (pos[id].empty()) {
		for (int i = id + 1; i < block_cnt; i++) {
			swap(pos[i - 1], pos[i]);
			swap(dp[i - 1], dp[i]);
		}
		block_cnt--;
	}
	else {
		calc_block(id);
	}
}

void add(int X) {
	int id = 0;
	while (id < block_cnt && pos[id].back() < X) {
		id++;
	}
	if (id == block_cnt) {
		block_cnt++;
	}
	pos[id].insert(upper_bound(pos[id].begin(), pos[id].end(), X), X);
	if ((int)pos[id].size() == block_size * 2) {
		for (int i = block_cnt - 1; i > id; i--) {
			swap(pos[i + 1], pos[i]);
			swap(dp[i + 1], dp[i]);
		}
		pos[id + 1].insert(pos[id + 1].begin(), pos[id].begin() + block_size, pos[id].end());
		pos[id].erase(pos[id].begin() + block_size, pos[id].end());
		block_cnt++;
		calc_block(id);
		calc_block(id + 1);
	}
	else {
		calc_block(id);
	}
}

void init(int _N, int _L, int _A[]) {
	N = _N;
	L = _L;
	block_cnt = (N - 1) / block_size + 1;
	for (int i = 0; i < N; i++) {
		A[i] = _A[i];
		pos[i / block_size].push_back(A[i]);
	}
	for (int id = 0; id < block_cnt; id++) {
		calc_block(id);
	}
}

int update(int i, int X) {
	rem(A[i]);
	A[i] = X;
	add(A[i]);
	return calc_all();
}

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