oj.uz

Submission #123431

# Submission time Handle Problem Language Result Execution time Memory
123431 2019-07-01T12:38:01 Z nxteru Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 3604 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 2000
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 380 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 380 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 380 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 7056 ms 1584 KB Output is correct
8 Correct 7089 ms 1796 KB Output is correct
9 Correct 6755 ms 3252 KB Output is correct
10 Correct 3417 ms 3320 KB Output is correct
11 Correct 3326 ms 3452 KB Output is correct
12 Correct 8137 ms 3604 KB Output is correct
13 Correct 3378 ms 3400 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 380 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 7056 ms 1584 KB Output is correct
8 Correct 7089 ms 1796 KB Output is correct
9 Correct 6755 ms 3252 KB Output is correct
10 Correct 3417 ms 3320 KB Output is correct
11 Correct 3326 ms 3452 KB Output is correct
12 Correct 8137 ms 3604 KB Output is correct
13 Correct 3378 ms 3400 KB Output is correct
14 Correct 8787 ms 2312 KB Output is correct
15 Execution timed out 9100 ms 2288 KB Time limit exceeded
16 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 380 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 7056 ms 1584 KB Output is correct
8 Correct 7089 ms 1796 KB Output is correct
9 Correct 6755 ms 3252 KB Output is correct
10 Correct 3417 ms 3320 KB Output is correct
11 Correct 3326 ms 3452 KB Output is correct
12 Correct 8137 ms 3604 KB Output is correct
13 Correct 3378 ms 3400 KB Output is correct
14 Correct 8787 ms 2312 KB Output is correct
15 Execution timed out 9100 ms 2288 KB Time limit exceeded
16 Halted 0 ms 0 KB -