oj.uz

Submission #123514

# Submission time Handle Problem Language Result Execution time Memory
123514 2019-07-01T14:13:33 Z nxteru Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 10228 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 150005
#define B 350
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/2){
		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 348 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 348 KB Output is correct
7 Correct 839 ms 2256 KB Output is correct
8 Correct 902 ms 2552 KB Output is correct
9 Correct 1245 ms 4008 KB Output is correct
10 Correct 1369 ms 3896 KB Output is correct
11 Correct 1322 ms 3908 KB Output is correct
12 Correct 2233 ms 3908 KB Output is correct
13 Correct 1271 ms 3832 KB Output is correct

Subtask #4
47.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 348 KB Output is correct
7 Correct 839 ms 2256 KB Output is correct
8 Correct 902 ms 2552 KB Output is correct
9 Correct 1245 ms 4008 KB Output is correct
10 Correct 1369 ms 3896 KB Output is correct
11 Correct 1322 ms 3908 KB Output is correct
12 Correct 2233 ms 3908 KB Output is correct
13 Correct 1271 ms 3832 KB Output is correct
14 Correct 1369 ms 2428 KB Output is correct
15 Correct 1401 ms 3064 KB Output is correct
16 Correct 3307 ms 4344 KB Output is correct
17 Correct 3930 ms 5240 KB Output is correct
18 Correct 4097 ms 5224 KB Output is correct
19 Correct 3455 ms 5224 KB Output is correct
20 Correct 3870 ms 5220 KB Output is correct
21 Correct 3897 ms 5216 KB Output is correct
22 Correct 2345 ms 5368 KB Output is correct

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 348 KB Output is correct
7 Correct 839 ms 2256 KB Output is correct
8 Correct 902 ms 2552 KB Output is correct
9 Correct 1245 ms 4008 KB Output is correct
10 Correct 1369 ms 3896 KB Output is correct
11 Correct 1322 ms 3908 KB Output is correct
12 Correct 2233 ms 3908 KB Output is correct
13 Correct 1271 ms 3832 KB Output is correct
14 Correct 1369 ms 2428 KB Output is correct
15 Correct 1401 ms 3064 KB Output is correct
16 Correct 3307 ms 4344 KB Output is correct
17 Correct 3930 ms 5240 KB Output is correct
18 Correct 4097 ms 5224 KB Output is correct
19 Correct 3455 ms 5224 KB Output is correct
20 Correct 3870 ms 5220 KB Output is correct
21 Correct 3897 ms 5216 KB Output is correct
22 Correct 2345 ms 5368 KB Output is correct
23 Correct 8282 ms 9884 KB Output is correct
24 Execution timed out 9010 ms 10228 KB Time limit exceeded
25 Halted 0 ms 0 KB -