oj.uz

답안 #123524

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123524 2019-07-01T14:23:06 Z nxteru 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
50 / 100
 9000 ms 6136 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 150005
#define B 360
int n,k,bs[MAX_N/B+2],p[MAX_N],pl[MAX_N],l,cnt,ds[MAX_N/B+2][B*3+1],sz[MAX_N/B+2][B*3+1],el[MAX_N/B+2][B*3+1];
void Bini(int x,int *xel,int xbs,int *xds,int *xsz){
	sort(xel,xel+xbs);
	int r=xbs;
	for(int i=xbs-1;i>=0;i--){
		while(r-1>=0&&xel[i]+l<xel[r-1])r--;
		if(r==xbs){
			xds[i]=xel[i]+l;
			xsz[i]=1;
		}else{
			xds[i]=xds[r];
			xsz[i]=xsz[r]+1;
		}
	}
}
void ALLini(void){
	for(int i=0;i<n;i++)pl[i]=p[i];
	sort(pl,pl+n);
	bs[0]=0;
	k=0;
	for(int i=0;i<n;i++){
		if(bs[k]>=B){
			k++;
			bs[k]=0;
		}
		el[k][bs[k]]=pl[i];
		bs[k]++;
	}
	for(int i=0;i<=k;i++)Bini(i,el[i],bs[i],ds[i],sz[i]);
}
void init(int N, int L, int X[]){
	n=N,l=L;
	for(int i=0;i<n;i++)p[i]=X[i];
	ALLini();
}
int update(int t, int y){
	int a=-1,b=p[t];
	while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0]<=b))a++;
	if(a==-1)a=0;
	for(int i=0;i<bs[a]-1;i++){
		if(el[a][i]==b){
			el[a][i]=el[a][bs[a]-1];
			break;
		}
	}
	bs[a]--;
	Bini(a,el[a],bs[a],ds[a],sz[a]);
	p[t]=y;
	a=-1;
	while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0]<=y))a++;
	if(a==-1)a=0;
	el[a][bs[a]]=y;
	bs[a]++;
	Bini(a,el[a],bs[a],ds[a],sz[a]);
	int ans=0;
	a=0,b=-1;
	for(;a<=k;a++){
		if(bs[a]==0)continue;
		int c=upper_bound(el[a],el[a]+bs[a],b)-el[a];
		if(c==bs[a])continue;
		ans+=sz[a][c];
		b=ds[a][c];
	}
	cnt++;
	if(cnt>=B){
		cnt=0;
		ALLini();
	}
	return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:43:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0]<=b))a++;
        ~~~~~~^~~~~~~~~~~~
elephants.cpp:55:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0]<=y))a++;
        ~~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 803 ms 1580 KB Output is correct
8 Correct 839 ms 1820 KB Output is correct
9 Correct 1029 ms 3336 KB Output is correct
10 Correct 980 ms 3340 KB Output is correct
11 Correct 960 ms 3356 KB Output is correct
12 Correct 1651 ms 3344 KB Output is correct
13 Correct 908 ms 3340 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 803 ms 1580 KB Output is correct
8 Correct 839 ms 1820 KB Output is correct
9 Correct 1029 ms 3336 KB Output is correct
10 Correct 980 ms 3340 KB Output is correct
11 Correct 960 ms 3356 KB Output is correct
12 Correct 1651 ms 3344 KB Output is correct
13 Correct 908 ms 3340 KB Output is correct
14 Correct 1170 ms 2060 KB Output is correct
15 Correct 1271 ms 2332 KB Output is correct
16 Correct 2629 ms 3580 KB Output is correct
17 Correct 2796 ms 4540 KB Output is correct
18 Correct 2892 ms 4472 KB Output is correct
19 Execution timed out 9019 ms 6136 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 803 ms 1580 KB Output is correct
8 Correct 839 ms 1820 KB Output is correct
9 Correct 1029 ms 3336 KB Output is correct
10 Correct 980 ms 3340 KB Output is correct
11 Correct 960 ms 3356 KB Output is correct
12 Correct 1651 ms 3344 KB Output is correct
13 Correct 908 ms 3340 KB Output is correct
14 Correct 1170 ms 2060 KB Output is correct
15 Correct 1271 ms 2332 KB Output is correct
16 Correct 2629 ms 3580 KB Output is correct
17 Correct 2796 ms 4540 KB Output is correct
18 Correct 2892 ms 4472 KB Output is correct
19 Execution timed out 9019 ms 6136 KB Time limit exceeded
20 Halted 0 ms 0 KB -