oj.uz

Submission #123432

# Submission time Handle Problem Language Result Execution time Memory
123432 2019-07-01T12:38:50 Z nxteru Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 6908 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 1000
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 3247 ms 1648 KB Output is correct
8 Correct 3273 ms 1900 KB Output is correct
9 Correct 3333 ms 3548 KB Output is correct
10 Correct 1802 ms 3564 KB Output is correct
11 Correct 1793 ms 3576 KB Output is correct
12 Correct 4121 ms 3908 KB Output is correct
13 Correct 1786 ms 3704 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 3247 ms 1648 KB Output is correct
8 Correct 3273 ms 1900 KB Output is correct
9 Correct 3333 ms 3548 KB Output is correct
10 Correct 1802 ms 3564 KB Output is correct
11 Correct 1793 ms 3576 KB Output is correct
12 Correct 4121 ms 3908 KB Output is correct
13 Correct 1786 ms 3704 KB Output is correct
14 Correct 4523 ms 2280 KB Output is correct
15 Correct 4683 ms 2428 KB Output is correct
16 Correct 6531 ms 3796 KB Output is correct
17 Correct 6395 ms 6908 KB Output is correct
18 Correct 6521 ms 6904 KB Output is correct
19 Execution timed out 9083 ms 6892 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 3247 ms 1648 KB Output is correct
8 Correct 3273 ms 1900 KB Output is correct
9 Correct 3333 ms 3548 KB Output is correct
10 Correct 1802 ms 3564 KB Output is correct
11 Correct 1793 ms 3576 KB Output is correct
12 Correct 4121 ms 3908 KB Output is correct
13 Correct 1786 ms 3704 KB Output is correct
14 Correct 4523 ms 2280 KB Output is correct
15 Correct 4683 ms 2428 KB Output is correct
16 Correct 6531 ms 3796 KB Output is correct
17 Correct 6395 ms 6908 KB Output is correct
18 Correct 6521 ms 6904 KB Output is correct
19 Execution timed out 9083 ms 6892 KB Time limit exceeded
20 Halted 0 ms 0 KB -