Submission #14762

# Submission time Handle Problem Language Result Execution time Memory
14762 2015-06-21T15:44:24 Z minsu Dancing Elephants (IOI11_elephants) C++14
Compilation error
0 ms 0 KB
// 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(); 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( temp, tmp+n );
		for(int i=0; i<bn; i++) pos[i].clear(), ans[i].clear(), lim[i].clear();
		init( n, K, tmp );
		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;
}

Compilation message

elephants.cpp: In function ‘void construct(int)’:
elephants.cpp:14:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if( p == pos[b].size() )
         ^
elephants.cpp: In function ‘int update(int, int)’:
elephants.cpp:40:45: error: ‘temp’ was not declared in this scope
   memcpy( tmp, ele, n * sizeof(int)); sort( temp, tmp+n );
                                             ^