답안 #59366 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59366	2018-07-21T19:44:22 Z	TadijaSebez	코끼리 (Dancing Elephants) (IOI11_elephants)	C++11	100 / 100	4710 ms	120028 KB

elephants

#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

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

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

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

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

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

답안 #59366

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 47.0 / 47.0

Subtask #5 3.0 / 3.0

Subtask #1
10.0 / 10.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
47.0 / 47.0

Subtask #5
3.0 / 3.0