oj.uz

답안 #17998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17998 2016-01-18T07:38:59 Z comet 코끼리 (Dancing Elephants) (IOI11_elephants) C++
97 / 100
 9000 ms 22632 KB 
#include <cstdio>
#include <algorithm>
using namespace std;

int N,M,L;
int B=400;

struct group{
	int sz,p[610],cnt[610],nxt[610];
	void init(){
		int id=sz-1;
		for(int i=sz-1;i>=0;i--){
			if(p[sz-1]-p[i]<=L)cnt[i]=1,nxt[i]=p[i]+L+1;
			else{
				while(p[id]-p[i]>L)id--;
				cnt[i]=cnt[id+1]+1;
				nxt[i]=nxt[id+1];
			}
		}
	}
	void push(int x){
		int id=0;
		while(id<sz&&p[id]<=x)id++;
		sz++;
		for(int i=sz-1;i>id;i--)p[i]=p[i-1];
		p[id]=x;
		init();
	}
	void pop(int x){
		int id=0;
		while(p[id]<=x)id++;
		for(int i=id;i<sz;i++)p[i-1]=p[i];
		sz--;
		init();
	}
}a[500];

struct elephant{
	int p,group_id,id;
	bool operator<(const elephant& r)const{
		return p<r.p;
	}
}b[150010];

int ID[150010];

void renewal(){
	sort(b,b+N);
	for(int i=0;i<M;i++)a[i].sz=0;
	for(int i=0;i<N;i++){
		ID[b[i].id]=i;
		b[i].group_id=i/B;
		a[i/B].p[a[i/B].sz++]=b[i].p;
		M=max(M,i/B+1);
	}
	for(int i=0;i<M;i++){
		a[i].init();
	}
}

void init(int N_, int L_, int X[]){
	N=N_;
	L=L_;
	for(int i=0;i<N;i++)b[i]=elephant{X[i],i/B,i};
	renewal();
}

int findGroup(int x){
	if(a[0].p[0]>x)return 0;
	for(int i=0;i<M-1;i++){
		if(a[i].p[0]<=x&&x<a[i+1].p[0])return i;
	}
	return M-1;
}

int calc(){
	int x=0,ret=0;
	for(int i=0;i<M;i++){
		int id=lower_bound(a[i].p,a[i].p+a[i].sz,x)-a[i].p;
		if(id==a[i].sz)continue;
		ret+=a[i].cnt[id];
		x=a[i].nxt[id];
	}
	return ret;
}

int update(int i, int y){

	int id=b[ID[i]].group_id;
	a[id].pop(b[ID[i]].p);
	b[ID[i]].p=y;
	if(a[id].sz<=200){
		renewal();
		return calc();
	}

	id=b[ID[i]].group_id=findGroup(y);
	a[id].push(y);
	if(a[id].sz>=600)renewal();
	return calc();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 22632 KB Output is correct
2 Correct 0 ms 22632 KB Output is correct
3 Correct 0 ms 22632 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 22632 KB Output is correct
2 Correct 0 ms 22632 KB Output is correct
3 Correct 0 ms 22632 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 475 ms 22632 KB Output is correct
2 Correct 316 ms 22632 KB Output is correct
3 Correct 411 ms 22632 KB Output is correct
4 Correct 2016 ms 22632 KB Output is correct
5 Correct 1993 ms 22632 KB Output is correct
6 Correct 639 ms 22632 KB Output is correct
7 Correct 2016 ms 22632 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 535 ms 22632 KB Output is correct
2 Correct 807 ms 22632 KB Output is correct
3 Correct 967 ms 22632 KB Output is correct
4 Correct 1035 ms 22632 KB Output is correct
5 Correct 1098 ms 22632 KB Output is correct
6 Correct 3907 ms 22632 KB Output is correct
7 Correct 1046 ms 22632 KB Output is correct
8 Correct 990 ms 22632 KB Output is correct
9 Correct 3930 ms 22632 KB Output is correct

Subtask #5
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2509 ms 22632 KB Output is correct
2 Correct 2513 ms 22632 KB Output is correct
3 Correct 2070 ms 22632 KB Output is correct
4 Execution timed out 9000 ms 22628 KB Program timed out
5 Halted 0 ms 0 KB -