oj.uz

Submission #59366

# Submission time Handle Problem Language Result Execution time Memory
59366 2018-07-21T19:44:22 Z TadijaSebez Dancing Elephants (IOI11_elephants) C++11
100 / 100
 4710 ms 120028 KB 
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=150050;
const int S=389;
int n,l;
struct Bucket
{
	int sz,dp[2*S],rng[2*N],x[2*S];
	Bucket(){ sz=0;}
	void Build()
	{
		int i,j=sz;
		for(i=sz-1;~i;i--)
		{
			while(j && x[i]+l<x[j-1]) j--;
			if(j==sz)
			{
				dp[i]=1;
				rng[i]=x[i]+l;
			}
			else
			{
				dp[i]=dp[j]+1;
				rng[i]=rng[j];
			}
		}
	}
	void Del(int y)
	{
		int i;
		for(i=0;i<sz;i++) if(x[i]==y) break;
		sz--;
		for(;i<sz;i++) x[i]=x[i+1];
		Build();
	}
	void Add(int y)
	{
		int i,j;
		for(i=0;i<sz;i++) if(x[i]>y) break;
		sz++;
		for(j=sz-1;j>i;j--) x[j]=x[j-1];
		x[i]=y;
		Build();
	}
	void Push(int y){ x[sz++]=y;}
} bk[S];
int pos[N],Timer,tmp[N];
void Rebuild()
{
	int cnt=0,i,j;
	for(i=0;i<S;i++)
	{
		for(j=0;j<bk[i].sz;j++) tmp[cnt++]=bk[i].x[j];
		bk[i].sz=0;
	}
	for(i=0;i<cnt;i++) bk[i/S].Push(tmp[i]);
	for(i=0;i<S;i++) bk[i].Build();
}
void init(int N, int L, int *X)
{
	n=N;l=L;int i;
	for(i=0;i<n;i++) pos[i]=X[i],bk[i/S].Push(pos[i]);
	for(i=0;i<S;i++) bk[i].Build();
	Timer=S-1;
}
int update(int id, int y)
{
	int i,j;
	for(i=0;i<S;i++) if(bk[i].sz==0 || bk[i].x[0]>pos[id]) break;
	if(i) i--;
	bk[i].Del(pos[id]);
	pos[id]=y;
	for(i=0;i<S;i++) if(bk[i].sz==0 || bk[i].x[0]>pos[id]) break;
	if(i) i--;
	bk[i].Add(pos[id]);
	int ans=0;
	int range=-1;
	for(i=0;i<S;i++)
	{
		if(!bk[i].sz) break;
		j=upper_bound(bk[i].x,bk[i].x+bk[i].sz,range)-bk[i].x;
		if(j==bk[i].sz) continue;
		ans+=bk[i].dp[j];
		range=bk[i].rng[j];
	}
	Timer--;
	if(!Timer) Rebuild(),Timer=S-1;
	return ans;
}
//----------------------//
/*
int X[N];
int main()
{
	int n,q,l,i,x;
	scanf("%i %i",&n,&l);
	for(i=0;i<n;i++) scanf("%i",&X[i]);
	init(n,l,X);
	scanf("%i",&q);
	while(q--)
	{
		scanf("%i %i",&i,&x);
		printf("%i\n",update(i,x));
	}
	return 0;
}
*/
//----------------------//

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2880 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2880 KB Output is correct
4 Correct 4 ms 2884 KB Output is correct
5 Correct 4 ms 3064 KB Output is correct
6 Correct 3 ms 3064 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2880 KB Output is correct
4 Correct 4 ms 2884 KB Output is correct
5 Correct 4 ms 3064 KB Output is correct
6 Correct 3 ms 3064 KB Output is correct
7 Correct 280 ms 4932 KB Output is correct
8 Correct 417 ms 6260 KB Output is correct
9 Correct 512 ms 8700 KB Output is correct
10 Correct 463 ms 10112 KB Output is correct
11 Correct 456 ms 11208 KB Output is correct
12 Correct 634 ms 12740 KB Output is correct
13 Correct 416 ms 13784 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2880 KB Output is correct
4 Correct 4 ms 2884 KB Output is correct
5 Correct 4 ms 3064 KB Output is correct
6 Correct 3 ms 3064 KB Output is correct
7 Correct 280 ms 4932 KB Output is correct
8 Correct 417 ms 6260 KB Output is correct
9 Correct 512 ms 8700 KB Output is correct
10 Correct 463 ms 10112 KB Output is correct
11 Correct 456 ms 11208 KB Output is correct
12 Correct 634 ms 12740 KB Output is correct
13 Correct 416 ms 13784 KB Output is correct
14 Correct 391 ms 14876 KB Output is correct
15 Correct 588 ms 16408 KB Output is correct
16 Correct 1187 ms 19044 KB Output is correct
17 Correct 1264 ms 21756 KB Output is correct
18 Correct 1297 ms 23788 KB Output is correct
19 Correct 756 ms 25896 KB Output is correct
20 Correct 1328 ms 28036 KB Output is correct
21 Correct 1322 ms 29824 KB Output is correct
22 Correct 930 ms 31472 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2880 KB Output is correct
4 Correct 4 ms 2884 KB Output is correct
5 Correct 4 ms 3064 KB Output is correct
6 Correct 3 ms 3064 KB Output is correct
7 Correct 280 ms 4932 KB Output is correct
8 Correct 417 ms 6260 KB Output is correct
9 Correct 512 ms 8700 KB Output is correct
10 Correct 463 ms 10112 KB Output is correct
11 Correct 456 ms 11208 KB Output is correct
12 Correct 634 ms 12740 KB Output is correct
13 Correct 416 ms 13784 KB Output is correct
14 Correct 391 ms 14876 KB Output is correct
15 Correct 588 ms 16408 KB Output is correct
16 Correct 1187 ms 19044 KB Output is correct
17 Correct 1264 ms 21756 KB Output is correct
18 Correct 1297 ms 23788 KB Output is correct
19 Correct 756 ms 25896 KB Output is correct
20 Correct 1328 ms 28036 KB Output is correct
21 Correct 1322 ms 29824 KB Output is correct
22 Correct 930 ms 31472 KB Output is correct
23 Correct 4315 ms 39940 KB Output is correct
24 Correct 3974 ms 44980 KB Output is correct
25 Correct 2716 ms 50004 KB Output is correct
26 Correct 3459 ms 55084 KB Output is correct
27 Correct 3130 ms 59940 KB Output is correct
28 Correct 1895 ms 59940 KB Output is correct
29 Correct 1810 ms 61308 KB Output is correct
30 Correct 1911 ms 64220 KB Output is correct
31 Correct 1849 ms 67416 KB Output is correct
32 Correct 3774 ms 76184 KB Output is correct
33 Correct 2767 ms 79952 KB Output is correct
34 Correct 3027 ms 84684 KB Output is correct
35 Correct 2583 ms 89648 KB Output is correct
36 Correct 3035 ms 93968 KB Output is correct
37 Correct 3285 ms 99300 KB Output is correct
38 Correct 3407 ms 102528 KB Output is correct
39 Correct 2644 ms 107208 KB Output is correct
40 Correct 3138 ms 110988 KB Output is correct
41 Correct 4408 ms 115504 KB Output is correct
42 Correct 4710 ms 120028 KB Output is correct