oj.uz

Submission #123504

# Submission time Handle Problem Language Result Execution time Memory
123504 2019-07-01T14:07:31 Z nxteru Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 10080 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#pragma gcc target "avx2"
#pragma gcc optimize "O3"
#pragma gcc optimize "unroll-roops"
using namespace std;
#define MAX_N 150005
#define B 350
int n,k,bs[MAX_N/B+2],p[MAX_N],pl[MAX_N],l,cnt,ds[MAX_N/B+2][B*3+1],sz[MAX_N/B+2][B*3+1],el[MAX_N/B+2][B*3+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:3:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
 #pragma gcc target "avx2"
 
elephants.cpp:4:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize "O3"
 
elephants.cpp:5:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize "unroll-roops"
 
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:46: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:58: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 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 782 ms 1696 KB Output is correct
8 Correct 817 ms 1920 KB Output is correct
9 Correct 1008 ms 3440 KB Output is correct
10 Correct 989 ms 3796 KB Output is correct
11 Correct 942 ms 3796 KB Output is correct
12 Correct 1636 ms 3804 KB Output is correct
13 Correct 897 ms 3960 KB Output is correct

Subtask #4
47.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 782 ms 1696 KB Output is correct
8 Correct 817 ms 1920 KB Output is correct
9 Correct 1008 ms 3440 KB Output is correct
10 Correct 989 ms 3796 KB Output is correct
11 Correct 942 ms 3796 KB Output is correct
12 Correct 1636 ms 3804 KB Output is correct
13 Correct 897 ms 3960 KB Output is correct
14 Correct 1166 ms 2548 KB Output is correct
15 Correct 1239 ms 2780 KB Output is correct
16 Correct 2489 ms 4088 KB Output is correct
17 Correct 2778 ms 4968 KB Output is correct
18 Correct 2895 ms 4984 KB Output is correct
19 Correct 3128 ms 5000 KB Output is correct
20 Correct 2740 ms 5012 KB Output is correct
21 Correct 2733 ms 4984 KB Output is correct
22 Correct 1614 ms 4988 KB Output is correct

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 782 ms 1696 KB Output is correct
8 Correct 817 ms 1920 KB Output is correct
9 Correct 1008 ms 3440 KB Output is correct
10 Correct 989 ms 3796 KB Output is correct
11 Correct 942 ms 3796 KB Output is correct
12 Correct 1636 ms 3804 KB Output is correct
13 Correct 897 ms 3960 KB Output is correct
14 Correct 1166 ms 2548 KB Output is correct
15 Correct 1239 ms 2780 KB Output is correct
16 Correct 2489 ms 4088 KB Output is correct
17 Correct 2778 ms 4968 KB Output is correct
18 Correct 2895 ms 4984 KB Output is correct
19 Correct 3128 ms 5000 KB Output is correct
20 Correct 2740 ms 5012 KB Output is correct
21 Correct 2733 ms 4984 KB Output is correct
22 Correct 1614 ms 4988 KB Output is correct
23 Correct 6201 ms 9956 KB Output is correct
24 Correct 6742 ms 10080 KB Output is correct
25 Correct 5343 ms 10048 KB Output is correct
26 Correct 6056 ms 10052 KB Output is correct
27 Execution timed out 9020 ms 9976 KB Time limit exceeded
28 Halted 0 ms 0 KB -