oj.uz

Submission #123524

# Submission time Handle Problem Language Result Execution time Memory
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

# 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 312 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 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

# 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 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

# 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 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

# 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 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 -