oj.uz

Submission #16426

# Submission time Handle Problem Language Result Execution time Memory
16426 2015-08-24T01:49:32 Z choyi0521 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 1375 ms 21296 KB 
#include "elephants.h"
#include<algorithm>
using namespace std;
const int MAX_N = 150000, MAX_RTN =387;
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 21292 KB Output is correct
2 Correct 0 ms 21288 KB Output is correct
3 Correct 0 ms 21292 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 21288 KB Output is correct
2 Correct 390 ms 21288 KB Output is correct
3 Correct 535 ms 21296 KB Output is correct
4 Correct 506 ms 21296 KB Output is correct
5 Correct 533 ms 21292 KB Output is correct
6 Correct 773 ms 21292 KB Output is correct
7 Correct 514 ms 21296 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 21296 KB Output is correct
2 Correct 649 ms 21292 KB Output is correct
3 Correct 1143 ms 21292 KB Output is correct
4 Correct 1317 ms 21292 KB Output is correct
5 Correct 1375 ms 21296 KB Output is correct
6 Correct 921 ms 21292 KB Output is correct
7 Correct 1316 ms 21292 KB Output is correct
8 Correct 1265 ms 21288 KB Output is correct
9 Correct 833 ms 21296 KB Output is correct

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 126 ms 21288 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -