oj.uz

Submission #123430

# Submission time Handle Problem Language Result Execution time Memory
123430 2019-07-01T12:36:26 Z nxteru Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 5624 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
#define F first
#define S second
#define MAX_N 150005
#define B 1600
int n,k,bs[MAX_N/B+1],p[MAX_N],l,cnt,ds[MAX_N/B+1][B*2+1],sz[MAX_N/B+1][B*2+1];
P id[MAX_N],el[MAX_N/B+1][B*2+1],pl[MAX_N];
void Bini(int x){
	sort(el[x],el[x]+bs[x]);
	for(int i=0;i<bs[x];i++)id[el[x][i].S]=P(x,i);
	int r=bs[x];
	for(int i=bs[x]-1;i>=0;i--){
		while(r-1>=0&&el[x][i].F+l<el[x][r-1].F)r--;
		if(r==bs[x]){
			ds[x][i]=el[x][i].F+l;
			sz[x][i]=1;
		}else{
			ds[x][i]=ds[x][r];
			sz[x][i]=sz[x][r]+1;
		}
	}
}
void ALLini(void){
	for(int i=0;i<n;i++)pl[i]=P(p[i],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];
		id[pl[i].S]=P(k,bs[k]);
		bs[k]++;
	}
	for(int i=0;i<=k;i++)Bini(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=id[t].F,b=id[t].S;
	if(b!=bs[a]-1)el[a][b]=el[a][bs[a]-1];
	bs[a]--;
	Bini(a);
	p[t]=y;
	a=-1;
	while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0].F<=y)){
		a++;
	}
	if(a==-1)a=0;
	el[a][bs[a]]=P(y,t);
	bs[a]++;
	Bini(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],P(b,n))-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:54:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0].F<=y)){
        ~~~~~~^~~~~~~~~~~~

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 5601 ms 1856 KB Output is correct
8 Correct 5769 ms 2084 KB Output is correct
9 Correct 5377 ms 3600 KB Output is correct
10 Correct 1698 ms 3576 KB Output is correct
11 Correct 1678 ms 4728 KB Output is correct
12 Correct 6332 ms 4984 KB Output is correct
13 Correct 1685 ms 4496 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 5601 ms 1856 KB Output is correct
8 Correct 5769 ms 2084 KB Output is correct
9 Correct 5377 ms 3600 KB Output is correct
10 Correct 1698 ms 3576 KB Output is correct
11 Correct 1678 ms 4728 KB Output is correct
12 Correct 6332 ms 4984 KB Output is correct
13 Correct 1685 ms 4496 KB Output is correct
14 Correct 7259 ms 3964 KB Output is correct
15 Correct 7937 ms 3748 KB Output is correct
16 Execution timed out 9031 ms 5624 KB Time limit exceeded
17 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 5601 ms 1856 KB Output is correct
8 Correct 5769 ms 2084 KB Output is correct
9 Correct 5377 ms 3600 KB Output is correct
10 Correct 1698 ms 3576 KB Output is correct
11 Correct 1678 ms 4728 KB Output is correct
12 Correct 6332 ms 4984 KB Output is correct
13 Correct 1685 ms 4496 KB Output is correct
14 Correct 7259 ms 3964 KB Output is correct
15 Correct 7937 ms 3748 KB Output is correct
16 Execution timed out 9031 ms 5624 KB Time limit exceeded
17 Halted 0 ms 0 KB -