oj.uz

답안 #17981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17981 2016-01-18T05:19:44 Z suhgyuho_william 코끼리 (Dancing Elephants) (IOI11_elephants) C++
26 / 100
 9000 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 update(int x,int y){
	//for(i=1; i<=m; i++){

		int i,j,k,m;
	int sum;
	int ans,e;
	int left,mid,right;
		//scanf("%d %d",&x,&y);
		del(a[x]);
		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(i%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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 9000 ms 23736 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 9000 ms 23736 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 9000 ms 23736 KB Program timed out
2 Halted 0 ms 0 KB -