oj.uz

Submission #123479

# Submission time Handle Problem Language Result Execution time Memory
123479 2019-07-01T13:47:52 Z nxteru Dancing Elephants (IOI11_elephants) C++14
97 / 100
 3123 ms 12116 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+1],p[MAX_N],pl[MAX_N],l,cnt,ds[MAX_N/B+1][B*2+1],sz[MAX_N/B+1][B*2+1],el[MAX_N/B+1][B*2+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){
		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 380 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 380 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 380 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 778 ms 1400 KB Output is correct
8 Correct 818 ms 1656 KB Output is correct
9 Correct 1010 ms 2808 KB Output is correct
10 Correct 986 ms 2680 KB Output is correct
11 Correct 940 ms 2808 KB Output is correct
12 Correct 1643 ms 2808 KB Output is correct
13 Correct 899 ms 2808 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 778 ms 1400 KB Output is correct
8 Correct 818 ms 1656 KB Output is correct
9 Correct 1010 ms 2808 KB Output is correct
10 Correct 986 ms 2680 KB Output is correct
11 Correct 940 ms 2808 KB Output is correct
12 Correct 1643 ms 2808 KB Output is correct
13 Correct 899 ms 2808 KB Output is correct
14 Correct 1172 ms 1860 KB Output is correct
15 Correct 1250 ms 2060 KB Output is correct
16 Correct 2491 ms 3064 KB Output is correct
17 Correct 2780 ms 3708 KB Output is correct
18 Correct 2911 ms 5668 KB Output is correct
19 Correct 3123 ms 5872 KB Output is correct
20 Correct 2743 ms 5868 KB Output is correct
21 Correct 2732 ms 5624 KB Output is correct
22 Correct 1613 ms 5240 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 778 ms 1400 KB Output is correct
8 Correct 818 ms 1656 KB Output is correct
9 Correct 1010 ms 2808 KB Output is correct
10 Correct 986 ms 2680 KB Output is correct
11 Correct 940 ms 2808 KB Output is correct
12 Correct 1643 ms 2808 KB Output is correct
13 Correct 899 ms 2808 KB Output is correct
14 Correct 1172 ms 1860 KB Output is correct
15 Correct 1250 ms 2060 KB Output is correct
16 Correct 2491 ms 3064 KB Output is correct
17 Correct 2780 ms 3708 KB Output is correct
18 Correct 2911 ms 5668 KB Output is correct
19 Correct 3123 ms 5872 KB Output is correct
20 Correct 2743 ms 5868 KB Output is correct
21 Correct 2732 ms 5624 KB Output is correct
22 Correct 1613 ms 5240 KB Output is correct
23 Incorrect 126 ms 12116 KB Output isn't correct
24 Halted 0 ms 0 KB -