Submission #1022777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022777		socpite	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	9069 ms	43872 KiB

elephants

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

const int blsz = 500;
const int maxn = 2e5+5;
const int INF = 2e9+5;

unordered_map<int, int> sp[18];
multiset<int> current;
multiset<int> changed;

int A[maxn];

int n, l;

void build_sp(){

	changed = {INF};

	sp[0].clear();
	for(auto v: current){
		if(v == INF)continue;
		sp[0][v] = *current.upper_bound(v + l);
	}
	sp[0][INF] = INF;
	for(int i = 1; i < 18; i++){
		sp[i].clear();
		for(auto v: current){
			sp[i][v] = sp[i-1][sp[i-1][v]];
		}
	}
}

void init(int N, int L, int X[])
{
  	n = N;
	l = L;
	current.insert(INF);
	for(int i = 0; i < N; i++){
		A[i] = X[i];
		current.insert(A[i]);
	}
	build_sp();
}

int update(int i, int y)
{
	current.erase(current.find(A[i]));
	changed.insert(A[i]);
	A[i] = y;
	current.insert(A[i]);
	changed.insert(A[i]);

	int realcnt = 0, ans = 0;
	int pos = *current.begin();
	while(pos != INF){
		realcnt++;
		if(changed.find(pos) != changed.end()){
			if(current.find(pos) == current.end())pos = *current.upper_bound(pos);
			else {
				ans++;
				pos = *current.upper_bound(pos + l);
			}
		}
		else {
			int nxt_change = *changed.upper_bound(pos);
			for(int i = 17; i >= 0; i--){
				if(sp[i][pos] < nxt_change){
					pos = sp[i][pos];
					ans += (1<<i);
				}
			}
			pos = *current.upper_bound(pos + l);
			ans++;
		}
	}
	if(realcnt >= blsz)build_sp();
	return ans;
}

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