oj.uz

Submission #123531

# Submission time Handle Problem Language Result Execution time Memory
123531 2019-07-01T14:30:57 Z nxteru Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 6436 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 150005
#define B 410
int n,k,bs[MAX_N/B+B],p[MAX_N],pl[MAX_N],l,cnt,ds[MAX_N/B+B][B*2+1],sz[MAX_N/B+B][B*2+1],el[MAX_N/B+B][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++;
        ~~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 891 ms 1528 KB Output is correct
8 Correct 928 ms 1636 KB Output is correct
9 Correct 1108 ms 2808 KB Output is correct
10 Correct 988 ms 2856 KB Output is correct
11 Correct 976 ms 2808 KB Output is correct
12 Correct 1712 ms 2808 KB Output is correct
13 Correct 923 ms 2808 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 891 ms 1528 KB Output is correct
8 Correct 928 ms 1636 KB Output is correct
9 Correct 1108 ms 2808 KB Output is correct
10 Correct 988 ms 2856 KB Output is correct
11 Correct 976 ms 2808 KB Output is correct
12 Correct 1712 ms 2808 KB Output is correct
13 Correct 923 ms 2808 KB Output is correct
14 Correct 1303 ms 1992 KB Output is correct
15 Correct 1371 ms 2168 KB Output is correct
16 Correct 2605 ms 3064 KB Output is correct
17 Correct 2825 ms 3832 KB Output is correct
18 Correct 2940 ms 3832 KB Output is correct
19 Execution timed out 9049 ms 6436 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 891 ms 1528 KB Output is correct
8 Correct 928 ms 1636 KB Output is correct
9 Correct 1108 ms 2808 KB Output is correct
10 Correct 988 ms 2856 KB Output is correct
11 Correct 976 ms 2808 KB Output is correct
12 Correct 1712 ms 2808 KB Output is correct
13 Correct 923 ms 2808 KB Output is correct
14 Correct 1303 ms 1992 KB Output is correct
15 Correct 1371 ms 2168 KB Output is correct
16 Correct 2605 ms 3064 KB Output is correct
17 Correct 2825 ms 3832 KB Output is correct
18 Correct 2940 ms 3832 KB Output is correct
19 Execution timed out 9049 ms 6436 KB Time limit exceeded
20 Halted 0 ms 0 KB -