제출 #14766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
14766		minsu	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	26 / 100	9000 ms	20792 KiB

elephants

// Jun 21 2015, minsu( github : https://github.com/minsuu/ )
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;

const int MAXN = 150015;
const int BLOCK = 400;
int n,bn, K, beg[BLOCK], ele[MAXN], tmp[MAXN], cooltime;
vector<int> pos[BLOCK], ans[BLOCK], lim[BLOCK];

void construct( int b ){
	for(int i = (int)pos[b].size()-1; i>=0; i--){
		int p = lower_bound( pos[b].begin(), pos[b].end(), pos[b][i] + K + 1 ) - pos[b].begin();
		if( p == pos[b].size() )
			ans[b][i] = 1, lim[b][i] = pos[b][i] + K + 1;
		else
			ans[b][i] = ans[b][p] + 1, lim[b][i] = lim[b][p];
	}
}

void init(int N, int L, int X[])
{
	n = N; K = L;
	for(int i=0; i<n; i++){
		int b = i / BLOCK; ele[i] = X[i];
		pos[b].push_back( X[i] );
		ans[b].push_back( 0 );
		lim[b].push_back( 0 );
	} bn = (n-1) / BLOCK + 1;
	for(int i=0;i<bn;i++){
		construct(i);
		beg[i] = pos[i].back();
	}
}

int update(int i, int y)
{
	if( cooltime == BLOCK ){
		ele[i] = y;
		memcpy( tmp, ele, n * sizeof(int)); sort( tmp, tmp+n );
		for(int i=0; i<bn; i++) pos[i].clear(), ans[i].clear(), lim[i].clear();
		for(int i=0; i<n; i++){
			int b = i / BLOCK;
			pos[b].push_back( tmp[i] );
			ans[b].push_back( 0 );
			lim[b].push_back( 0 );
		}
		for(int i=0;i<bn;i++){
			construct(i);
			beg[i] = pos[i].back();
		}
		cooltime = 0;
	}else{
		int x = ele[i]; ele[i] = y; cooltime++;
		int xb = lower_bound( beg, beg+bn, x ) - beg;
		int xp = lower_bound( pos[xb].begin(), pos[xb].end(), x) - pos[xb].begin();
		pos[xb].erase( pos[xb].begin() + xp ); ans[xb].pop_back(); lim[xb].pop_back();
		construct(xb);
		if( pos[xb].size() != 0) beg[xb] = pos[xb].back();

		int yb = lower_bound( beg, beg+bn, y ) - beg; if( yb == bn ) yb--;
		int yp = lower_bound( pos[yb].begin(), pos[yb].end(), y) - pos[yb].begin();
		pos[yb].insert( pos[yb].begin() + yp, y ); ans[yb].push_back(0); lim[yb].push_back(0);
		construct(yb); beg[yb] = pos[yb].back();
	}

	int np = 0, ret = 0;
	for(int i=0; i<bn; i++){
		int sp = lower_bound( pos[i].begin(), pos[i].end(), np ) - pos[i].begin();
		ret += ans[i][sp]; np = lim[i][sp];
	}
	return ret;
}

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