oj.uz

Submission #17982

# Submission time Handle Problem Language Result Execution time Memory
17982 2016-01-18T05:21:53 Z suhgyuho_william Dancing Elephants (IOI11_elephants) C++
100 / 100
 3775 ms 23740 KB 
#include <stdio.h>
#include "elephants.h"

#define Size 390

int n,L;
int bucket[500][1000];
int last[500][1000],picture[500][1000];
int cnt[500];
int a[150002];

void setting(int x){
	int i,t;

	if(cnt[x] == 0) return;

	last[x][cnt[x]-1] = bucket[x][cnt[x]-1]+L;
	picture[x][cnt[x]-1] = 1;
	t = cnt[x]-1;
	for(i=cnt[x]-2; i>=0; i--){
		while(true){
			if(bucket[x][t-1]-bucket[x][i] > L) t--;
			else break;
		}
		if(bucket[x][cnt[x]-1]-bucket[x][i] <= L){
			last[x][i] = bucket[x][i]+L;
			picture[x][i] = 1;
		}else{
			last[x][i] = last[x][t];
			picture[x][i] = picture[x][t]+1;
		}
	}
}

int w,t;

void del(int x){
	int i;

	for(i=0; ; i++){
		if(cnt[i] > 0 && bucket[i][cnt[i]-1] >= x) break;
	}
	w = i;
	for(i=0; i<cnt[w]; i++){
		if(x == bucket[w][i]) break;
	}
	t = i;

	for(i=t+1; i<cnt[w]; i++){
		bucket[w][i-1] = bucket[w][i];
	}
	cnt[w]--;
	setting(w);
}

void add(int x){
	int i,sum;

	sum = 0;
	for(i=0; ; i++){
		if(cnt[i] > 0 && bucket[i][cnt[i]-1] > x) break;
		sum += cnt[i];
		if(sum == n-1) break;
	}
	w = i;
    if(sum == n-1){
		bucket[w][cnt[w]] = x;
    }else{
		for(i=0; i<cnt[w]; i++){
			if(bucket[w][i] > x) break;
		}
		t = i;
		for(i=cnt[w]; i>t; i--) bucket[w][i] = bucket[w][i-1];
		bucket[w][t] = x;
    }
    cnt[w]++;
    setting(w);
}

int tmp[150002];
void Bucketset(){
	int i,j;
	int sum,rear;

	sum = 0;
	rear = -1;
	for(i=0; ; i++){
		if(cnt[i] == 0) continue;
		sum += cnt[i];
		for(j=0; j<cnt[i]; j++) tmp[++rear] = bucket[i][j];
		cnt[i] = 0;
		if(sum == n) break;
	}
	for(i=0; i<=rear; i++){
		bucket[i/Size][i%Size] = tmp[i];
		cnt[i/Size]++;
	}
	for(i=0; i<=(rear/Size); i++) setting(i);
}

void mmain(void){
	int i,j,k,m;
	int x,y,sum;
	int ans,e;
	int left,mid,right;
	//freopen("input.txt","r",stdin);

	for(i=0; i<n; i++){
		bucket[i/Size][i%Size] = a[i];
		cnt[i/Size]++;
	}
	for(i=0; i<=(n-1)/Size; i++){
		setting(i);
	}
}
int ccnt = 0;
int update(int x,int y){
	int j,k,m;
	int sum;
	int ans,e;
	int left,mid,right;
	del(a[x]);
	ccnt++;
	add(y);
	a[x] = y;
	sum = 0;
	ans = 0;
	e = -1;
	for(j=0; ; j++){
		if(sum == n) break;
		if(cnt[j] == 0) continue;
		sum += cnt[j];
		if(e < bucket[j][0]){
			e = last[j][0];
			ans += picture[j][0];
		}else if(bucket[j][cnt[j]-1] > e){
			left = 0;
			right = cnt[j]-1;
			while(true){
				mid = (left+right)/2;
				if(bucket[j][mid] <= e && bucket[j][mid+1] > e) break;
				if(bucket[j][mid] > e) right = mid-1;
				else left = mid+1;
			}
			e = last[j][mid+1];
			ans += picture[j][mid+1];
		}
	}
	if(ccnt%Size == 0) Bucketset();
	return ans;
}

void init(int N, int ll, int X[])
{
	int i;
	n = N;
	L = ll;
	for(i=0; i<n; i++) a[i] = X[i];
	mmain();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 23740 KB Output is correct
2 Correct 387 ms 23740 KB Output is correct
3 Correct 410 ms 23740 KB Output is correct
4 Correct 340 ms 23740 KB Output is correct
5 Correct 308 ms 23740 KB Output is correct
6 Correct 710 ms 23740 KB Output is correct
7 Correct 413 ms 23740 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 23740 KB Output is correct
2 Correct 599 ms 23740 KB Output is correct
3 Correct 1154 ms 23740 KB Output is correct
4 Correct 1153 ms 23740 KB Output is correct
5 Correct 1329 ms 23740 KB Output is correct
6 Correct 849 ms 23740 KB Output is correct
7 Correct 1166 ms 23740 KB Output is correct
8 Correct 1166 ms 23740 KB Output is correct
9 Correct 759 ms 23740 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2976 ms 23740 KB Output is correct
2 Correct 3243 ms 23740 KB Output is correct
3 Correct 2013 ms 23740 KB Output is correct
4 Correct 3130 ms 23740 KB Output is correct
5 Correct 3230 ms 23740 KB Output is correct
6 Correct 1875 ms 23740 KB Output is correct
7 Correct 1741 ms 23740 KB Output is correct
8 Correct 1869 ms 23740 KB Output is correct
9 Correct 1783 ms 23740 KB Output is correct
10 Correct 1854 ms 23740 KB Output is correct
11 Correct 1445 ms 23740 KB Output is correct
12 Correct 2373 ms 23740 KB Output is correct
13 Correct 1383 ms 23740 KB Output is correct
14 Correct 1281 ms 23740 KB Output is correct
15 Correct 2625 ms 23740 KB Output is correct
16 Correct 3244 ms 23740 KB Output is correct
17 Correct 3138 ms 23740 KB Output is correct
18 Correct 3155 ms 23740 KB Output is correct
19 Correct 3666 ms 23740 KB Output is correct
20 Correct 3775 ms 23740 KB Output is correct