oj.uz

Submission #16425

# Submission time Handle Problem Language Result Execution time Memory
16425 2015-08-23T16:41:11 Z choyi0521 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 4331 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 21316 KB Output is correct
2 Correct 0 ms 21312 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 0 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 319 ms 21312 KB Output is correct
2 Correct 396 ms 21316 KB Output is correct
3 Correct 537 ms 21312 KB Output is correct
4 Correct 525 ms 21312 KB Output is correct
5 Correct 519 ms 21312 KB Output is correct
6 Correct 734 ms 21312 KB Output is correct
7 Correct 493 ms 21316 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 21312 KB Output is correct
2 Correct 653 ms 21316 KB Output is correct
3 Correct 1143 ms 21312 KB Output is correct
4 Correct 1323 ms 21308 KB Output is correct
5 Correct 1372 ms 21312 KB Output is correct
6 Correct 935 ms 21312 KB Output is correct
7 Correct 1329 ms 21312 KB Output is correct
8 Correct 1281 ms 21316 KB Output is correct
9 Correct 840 ms 21316 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3599 ms 21312 KB Output is correct
2 Correct 3775 ms 21316 KB Output is correct
3 Correct 3010 ms 21316 KB Output is correct
4 Correct 3029 ms 21308 KB Output is correct
5 Correct 3346 ms 21312 KB Output is correct
6 Correct 646 ms 21316 KB Output is correct
7 Correct 621 ms 21316 KB Output is correct
8 Correct 669 ms 21308 KB Output is correct
9 Correct 599 ms 21316 KB Output is correct
10 Correct 3059 ms 21308 KB Output is correct
11 Correct 2593 ms 21312 KB Output is correct
12 Correct 2729 ms 21316 KB Output is correct
13 Correct 2899 ms 21316 KB Output is correct
14 Correct 2658 ms 21316 KB Output is correct
15 Correct 3601 ms 21312 KB Output is correct
16 Correct 2697 ms 21312 KB Output is correct
17 Correct 2986 ms 21312 KB Output is correct
18 Correct 2682 ms 21316 KB Output is correct
19 Correct 4259 ms 21316 KB Output is correct
20 Correct 4331 ms 21312 KB Output is correct