제출 #1022796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022796		socpite	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	97 / 100	9041 ms	31688 KiB

elephants

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

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

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

int A[maxn];
int dval[maxn];

int n, l;

void build_sp(){

	changed = {INF};
	vmap.clear();
	int crr = 0;
	for(auto v: current)if(!crr || dval[crr-1] != v){
		vmap[v] = crr;
		dval[crr++] = v;
	}
	for(int i = 0; i < crr-1; i++){
		sp[0][i] = upper_bound(dval, dval + crr, dval[i] + l) - dval;
	}
	sp[0][crr-1] = crr-1;
	for(int i = 1; i < 18; i++){
		for(int j = 0; j < crr; j++)sp[i][j] = sp[i-1][sp[i-1][j]];
	}
}

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);
			int id = vmap[pos];
			for(int i = 17; i >= 0; i--){
				if(dval[sp[i][id]] < nxt_change){
					id = sp[i][id];
					ans += (1<<i);
				}
			}
			pos = *current.upper_bound(dval[id] + l);
			ans++;
		}
	}
	if(realcnt >= blsz)build_sp();
	return ans;
}

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