oj.uz

Submission #14766

# Submission time Handle Problem Language Result Execution time Memory
14766 2015-06-21T15:54:13 Z minsu Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 20792 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()-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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18552 KB Output is correct
2 Correct 0 ms 18552 KB Output is correct
3 Correct 0 ms 18552 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18552 KB Output is correct
2 Correct 2 ms 18552 KB Output is correct
3 Correct 0 ms 18552 KB Output is correct

Subtask #3
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2260 ms 18948 KB Output is correct
2 Incorrect 1889 ms 19080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 18816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9000 ms 20792 KB Program timed out
2 Halted 0 ms 0 KB -