oj.uz

Submission #18002

# Submission time Handle Problem Language Result Execution time Memory
18002 2016-01-18T07:56:18 Z comet Dancing Elephants (IOI11_elephants) C++
97 / 100
 9000 ms 22380 KB 
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

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

int sz[400],p[400][710],cnt[400][710],nxt[400][710];

void bucket_init(int k){
	int id=sz[k]-1;
	for(int i=sz[k]-1;i>=0;i--){
		if(p[k][sz[k]-1]-p[k][i]<=L)cnt[k][i]=1,nxt[k][i]=p[k][i]+L+1;
		else{
			while(p[k][id]-p[k][i]>L)id--;
			cnt[k][i]=cnt[k][id+1]+1;
			nxt[k][i]=nxt[k][id+1];
		}
	}
}

void push(int k,int x){
	int id=0;
	while(id<sz[k]&&p[k][id]<=x)id++;
	sz[k]++;
	for(int i=sz[k]-1;i>id;i--)p[k][i]=p[k][i-1];
	p[k][id]=x;
	bucket_init(k);
}
void pop(int k,int x){
	int id=0;
	while(p[k][id]<=x)id++;
	for(int i=id;i<sz[k];i++)p[k][i-1]=p[k][i];
	sz[k]--;
	bucket_init(k);
}

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);
	memset(sz,0,sizeof(sz));
	for(int i=0;i<N;i++){
		ID[b[i].id]=i;
		b[i].group_id=i/B;
		p[i/B][sz[i/B]++]=b[i].p;
		M=max(M,i/B+1);
	}
	for(int i=0;i<M;i++){
		bucket_init(i);
	}
}

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(p[0][0]>x)return 0;
	for(int i=0;i<M-1;i++){
		if(p[i][0]<=x&&x<p[i+1][0])return i;
	}
	return M-1;
}

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

int update(int i, int y){

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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 22380 KB Output is correct
2 Correct 15 ms 22380 KB Output is correct
3 Correct 19 ms 22380 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 22380 KB Output is correct
2 Correct 306 ms 22380 KB Output is correct
3 Correct 390 ms 22380 KB Output is correct
4 Correct 1427 ms 22380 KB Output is correct
5 Correct 1438 ms 22380 KB Output is correct
6 Correct 613 ms 22380 KB Output is correct
7 Correct 1444 ms 22380 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 22380 KB Output is correct
2 Correct 469 ms 22380 KB Output is correct
3 Correct 961 ms 22380 KB Output is correct
4 Correct 1015 ms 22380 KB Output is correct
5 Correct 1079 ms 22380 KB Output is correct
6 Correct 3258 ms 22380 KB Output is correct
7 Correct 1015 ms 22380 KB Output is correct
8 Correct 968 ms 22380 KB Output is correct
9 Correct 2780 ms 22380 KB Output is correct

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2499 ms 22380 KB Output is correct
2 Correct 2593 ms 22380 KB Output is correct
3 Correct 2176 ms 22380 KB Output is correct
4 Execution timed out 9000 ms 22376 KB Program timed out
5 Halted 0 ms 0 KB -