oj.uz

Submission #123465

# Submission time Handle Problem Language Result Execution time Memory
123465 2019-07-01T13:31:40 Z nxteru Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 5208 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 150005
#define B 1300
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++;
        ~~~~~~^~~~~~~~~~~~

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 364 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 364 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 420 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 364 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 420 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3766 ms 1536 KB Output is correct
8 Correct 3809 ms 1704 KB Output is correct
9 Correct 3786 ms 2764 KB Output is correct
10 Correct 1441 ms 2808 KB Output is correct
11 Correct 1424 ms 2780 KB Output is correct
12 Correct 4543 ms 2940 KB Output is correct
13 Correct 1405 ms 2800 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 364 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 420 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3766 ms 1536 KB Output is correct
8 Correct 3809 ms 1704 KB Output is correct
9 Correct 3786 ms 2764 KB Output is correct
10 Correct 1441 ms 2808 KB Output is correct
11 Correct 1424 ms 2780 KB Output is correct
12 Correct 4543 ms 2940 KB Output is correct
13 Correct 1405 ms 2800 KB Output is correct
14 Correct 4860 ms 2332 KB Output is correct
15 Correct 5500 ms 2124 KB Output is correct
16 Correct 7153 ms 3000 KB Output is correct
17 Correct 6911 ms 3960 KB Output is correct
18 Correct 7152 ms 3832 KB Output is correct
19 Execution timed out 9029 ms 5208 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 364 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 420 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3766 ms 1536 KB Output is correct
8 Correct 3809 ms 1704 KB Output is correct
9 Correct 3786 ms 2764 KB Output is correct
10 Correct 1441 ms 2808 KB Output is correct
11 Correct 1424 ms 2780 KB Output is correct
12 Correct 4543 ms 2940 KB Output is correct
13 Correct 1405 ms 2800 KB Output is correct
14 Correct 4860 ms 2332 KB Output is correct
15 Correct 5500 ms 2124 KB Output is correct
16 Correct 7153 ms 3000 KB Output is correct
17 Correct 6911 ms 3960 KB Output is correct
18 Correct 7152 ms 3832 KB Output is correct
19 Execution timed out 9029 ms 5208 KB Time limit exceeded
20 Halted 0 ms 0 KB -