oj.uz

Submission #124105

# Submission time Handle Problem Language Result Execution time Memory
124105 2019-07-02T14:19:41 Z nxteru Dancing Elephants (IOI11_elephants) C++14
50 / 100
 710 ms 3064 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 150005
#define B 600
int n,k,bs[MAX_N/B+2],p[MAX_N],pl[MAX_N],l,cnt,ds[MAX_N/B+2][B*2+1],sz[MAX_N/B+2][B*2+1],el[MAX_N/B+2][B*2+1];
void Bini(int x,int *xel,int xbs,int *xds,int *xsz){
	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(bool start){
	if(start)for(int i=0;i<n;i++)pl[i]=p[i];
	else{
		int sx=0;
		for(int i=0;i<=k;i++)for(int j=0;j<bs[i];j++)pl[sx++]=el[i][j];
	}
	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(1);
}
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;
	bool sw=false;
	for(int i=0;i<bs[a]-1;i++){
		if(el[a][i]==b)sw=true;
		if(sw)el[a][i]=el[a][i+1];
	}
	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]++;
	for(int i=bs[a]-1;i>0;i--)if(el[a][i]<el[a][i-1])swap(el[a][i],el[a][i-1]);
	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(0);
	}
	return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:45: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:56: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 380 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 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 376 ms 1696 KB Output is correct
8 Correct 389 ms 1912 KB Output is correct
9 Correct 466 ms 3060 KB Output is correct
10 Correct 325 ms 3036 KB Output is correct
11 Correct 328 ms 3064 KB Output is correct
12 Correct 710 ms 3028 KB Output is correct
13 Correct 327 ms 3064 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 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 376 ms 1696 KB Output is correct
8 Correct 389 ms 1912 KB Output is correct
9 Correct 466 ms 3060 KB Output is correct
10 Correct 325 ms 3036 KB Output is correct
11 Correct 328 ms 3064 KB Output is correct
12 Correct 710 ms 3028 KB Output is correct
13 Correct 327 ms 3064 KB Output is correct
14 Incorrect 360 ms 2120 KB Output isn't correct
15 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 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 376 ms 1696 KB Output is correct
8 Correct 389 ms 1912 KB Output is correct
9 Correct 466 ms 3060 KB Output is correct
10 Correct 325 ms 3036 KB Output is correct
11 Correct 328 ms 3064 KB Output is correct
12 Correct 710 ms 3028 KB Output is correct
13 Correct 327 ms 3064 KB Output is correct
14 Incorrect 360 ms 2120 KB Output isn't correct
15 Halted 0 ms 0 KB -