oj.uz

Submission #123446

# Submission time Handle Problem Language Result Execution time Memory
123446 2019-07-01T12:51:33 Z nxteru Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 3832 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 1600
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,P *xel,int xbs,int *xds,int *xsz){
	sort(xel,xel+xbs);
	for(int i=0;i<xbs;i++)id[xel[i].S]=P(x,i);
	int r=xbs;
	for(int i=xbs-1;i>=0;i--){
		while(r-1>=0&&xel[i].F+l<xel[r-1].F)r--;
		if(r==xbs){
			xds[i]=xel[i].F+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(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,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=id[t].F,b=id[t].S;
	if(b!=bs[a]-1)el[a][b]=el[a][bs[a]-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].F<=y)){
		a++;
	}
	if(a==-1)a=0;
	el[a][bs[a]]=P(y,t);
	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],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 3 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 3 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 5218 ms 1580 KB Output is correct
8 Correct 5284 ms 1816 KB Output is correct
9 Correct 5183 ms 3348 KB Output is correct
10 Correct 1731 ms 3320 KB Output is correct
11 Correct 1614 ms 3320 KB Output is correct
12 Correct 6098 ms 3576 KB Output is correct
13 Correct 1611 ms 3320 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 3 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 5218 ms 1580 KB Output is correct
8 Correct 5284 ms 1816 KB Output is correct
9 Correct 5183 ms 3348 KB Output is correct
10 Correct 1731 ms 3320 KB Output is correct
11 Correct 1614 ms 3320 KB Output is correct
12 Correct 6098 ms 3576 KB Output is correct
13 Correct 1611 ms 3320 KB Output is correct
14 Correct 7087 ms 2408 KB Output is correct
15 Correct 7404 ms 2424 KB Output is correct
16 Execution timed out 9041 ms 3832 KB Time limit exceeded
17 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 3 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 5218 ms 1580 KB Output is correct
8 Correct 5284 ms 1816 KB Output is correct
9 Correct 5183 ms 3348 KB Output is correct
10 Correct 1731 ms 3320 KB Output is correct
11 Correct 1614 ms 3320 KB Output is correct
12 Correct 6098 ms 3576 KB Output is correct
13 Correct 1611 ms 3320 KB Output is correct
14 Correct 7087 ms 2408 KB Output is correct
15 Correct 7404 ms 2424 KB Output is correct
16 Execution timed out 9041 ms 3832 KB Time limit exceeded
17 Halted 0 ms 0 KB -