답안 #123459

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123459 2019-07-01T13:27:33 Z nxteru 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
50 / 100
9000 ms 7100 KB
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 150005
#define B 1600
int n,k,bs[MAX_N/B+1],p[MAX_N],pl[MAX_N],l,cnt,ds[MAX_N/B+1][B*2+1],sz[MAX_N/B+1][B*2+1],el[MAX_N/B+1][B*2+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++;
        ~~~~~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4889 ms 2296 KB Output is correct
8 Correct 4982 ms 2552 KB Output is correct
9 Correct 4659 ms 4092 KB Output is correct
10 Correct 1465 ms 3896 KB Output is correct
11 Correct 1404 ms 3832 KB Output is correct
12 Correct 5589 ms 4104 KB Output is correct
13 Correct 1405 ms 3688 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4889 ms 2296 KB Output is correct
8 Correct 4982 ms 2552 KB Output is correct
9 Correct 4659 ms 4092 KB Output is correct
10 Correct 1465 ms 3896 KB Output is correct
11 Correct 1404 ms 3832 KB Output is correct
12 Correct 5589 ms 4104 KB Output is correct
13 Correct 1405 ms 3688 KB Output is correct
14 Correct 5627 ms 3436 KB Output is correct
15 Correct 6946 ms 3368 KB Output is correct
16 Correct 8785 ms 4600 KB Output is correct
17 Correct 8369 ms 5560 KB Output is correct
18 Correct 8643 ms 5624 KB Output is correct
19 Execution timed out 9078 ms 7100 KB Time limit exceeded
20 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4889 ms 2296 KB Output is correct
8 Correct 4982 ms 2552 KB Output is correct
9 Correct 4659 ms 4092 KB Output is correct
10 Correct 1465 ms 3896 KB Output is correct
11 Correct 1404 ms 3832 KB Output is correct
12 Correct 5589 ms 4104 KB Output is correct
13 Correct 1405 ms 3688 KB Output is correct
14 Correct 5627 ms 3436 KB Output is correct
15 Correct 6946 ms 3368 KB Output is correct
16 Correct 8785 ms 4600 KB Output is correct
17 Correct 8369 ms 5560 KB Output is correct
18 Correct 8643 ms 5624 KB Output is correct
19 Execution timed out 9078 ms 7100 KB Time limit exceeded
20 Halted 0 ms 0 KB -