oj.uz

Submission #16427

# Submission time Handle Problem Language Result Execution time Memory
16427 2015-08-24T01:50:17 Z choyi0521 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 4283 ms 21316 KB 
#include "elephants.h"
#include<algorithm>
using namespace std;
const int MAX_N = 150000, MAX_RTN =388;
int n,l,x[MAX_N];
int rtn;
struct st{
	int sz;
	int x[MAX_RTN*2],d[MAX_RTN * 2],cnt[MAX_RTN*2];
}e[MAX_RTN];
void init(int N, int L, int X[]){
	n = N;
	l = L;
	rtn = sqrt(N-1)+1;
	for (int i = 0; i < N; i++)
		e[i / rtn].x[e[i / rtn].sz++]=x[i] = X[i];
}
void UpdateBucket(int b){
	int tpos = e[b].sz;
	for (int i = e[b].sz - 1; i >= 0; i--){
		while (e[b].x[tpos - 1] - e[b].x[i] > l) tpos--;
		if (tpos == e[b].sz){
			e[b].d[i] = e[b].x[i];
			e[b].cnt[i] = 1;
		}
		else{
			e[b].d[i] = e[b].d[tpos];
			e[b].cnt[i] = e[b].cnt[tpos] + 1;
		}
	}
}
void Restructure(){
	int tx[MAX_N],tcnt=0;
	for (int i = 0; i < rtn; i++){
		for (int j = 0; j < e[i].sz; j++)
			tx[tcnt++] = e[i].x[j];
		e[i].sz = 0;
	}
	for (int i = 0; i < n; i++)
		e[i / rtn].x[e[i / rtn].sz++] = tx[i];
	for (int i = 0; i < rtn; i++) UpdateBucket(i);
}
void Delete(int tx){
	int b,i;
	for (b = 0; b < rtn; b++)
		if (e[b].sz && tx <= e[b].x[e[b].sz - 1]) break;
	if(b==rtn) b--;
	for (i = 0; e[b].x[i] != tx; i++);
	e[b].sz--;
	for (; i<e[b].sz; i++) e[b].x[i] = e[b].x[i + 1];
	UpdateBucket(b);
}
void Add(int tx){
	int b;
	for (b = 0; b < rtn; b++)
		if (e[b].sz && tx <= e[b].x[e[b].sz - 1]) break;
	if (b == rtn) b--;
	for (int i = 0; i < e[b].sz; i++)
		if (e[b].x[i]>tx) swap(e[b].x[i], tx);
	e[b].x[e[b].sz++] = tx;
	UpdateBucket(b);
}
int ucnt;
int update(int i, int y){
	if (ucnt++%rtn == 0) Restructure();
	Delete(x[i]);
	Add(x[i] = y);
	int ans = 0, b=-1, tx=-1, t;
	while (++b < rtn){
		t = upper_bound(e[b].x, e[b].x + e[b].sz, tx) - e[b].x;
		if (t == e[b].sz) continue;
		ans += e[b].cnt[t];
		tx = e[b].d[t] + l;
	}
	return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 21316 KB Output is correct
2 Correct 389 ms 21312 KB Output is correct
3 Correct 550 ms 21308 KB Output is correct
4 Correct 518 ms 21316 KB Output is correct
5 Correct 520 ms 21316 KB Output is correct
6 Correct 745 ms 21312 KB Output is correct
7 Correct 503 ms 21312 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 21316 KB Output is correct
2 Correct 635 ms 21312 KB Output is correct
3 Correct 1139 ms 21316 KB Output is correct
4 Correct 1345 ms 21316 KB Output is correct
5 Correct 1486 ms 21308 KB Output is correct
6 Correct 971 ms 21316 KB Output is correct
7 Correct 1336 ms 21316 KB Output is correct
8 Correct 1295 ms 21312 KB Output is correct
9 Correct 869 ms 21312 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3680 ms 21312 KB Output is correct
2 Correct 3817 ms 21316 KB Output is correct
3 Correct 3022 ms 21312 KB Output is correct
4 Correct 3053 ms 21312 KB Output is correct
5 Correct 3312 ms 21312 KB Output is correct
6 Correct 679 ms 21312 KB Output is correct
7 Correct 623 ms 21312 KB Output is correct
8 Correct 644 ms 21316 KB Output is correct
9 Correct 598 ms 21308 KB Output is correct
10 Correct 3079 ms 21312 KB Output is correct
11 Correct 2580 ms 21312 KB Output is correct
12 Correct 2702 ms 21312 KB Output is correct
13 Correct 3008 ms 21316 KB Output is correct
14 Correct 2650 ms 21312 KB Output is correct
15 Correct 3543 ms 21312 KB Output is correct
16 Correct 2683 ms 21316 KB Output is correct
17 Correct 3066 ms 21316 KB Output is correct
18 Correct 2705 ms 21312 KB Output is correct
19 Correct 4283 ms 21316 KB Output is correct
20 Correct 4278 ms 21312 KB Output is correct