oj.uz

Submission #123442

# Submission time Handle Problem Language Result Execution time Memory
123442 2019-07-01T12:46:16 Z nxteru Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 5448 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 1000
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 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 3054 ms 1656 KB Output is correct
8 Correct 3074 ms 2012 KB Output is correct
9 Correct 3216 ms 3704 KB Output is correct
10 Correct 1822 ms 3676 KB Output is correct
11 Correct 1723 ms 3704 KB Output is correct
12 Correct 4011 ms 3836 KB Output is correct
13 Correct 1715 ms 3708 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 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 3054 ms 1656 KB Output is correct
8 Correct 3074 ms 2012 KB Output is correct
9 Correct 3216 ms 3704 KB Output is correct
10 Correct 1822 ms 3676 KB Output is correct
11 Correct 1723 ms 3704 KB Output is correct
12 Correct 4011 ms 3836 KB Output is correct
13 Correct 1715 ms 3708 KB Output is correct
14 Correct 4486 ms 2324 KB Output is correct
15 Correct 4435 ms 2448 KB Output is correct
16 Correct 6358 ms 3880 KB Output is correct
17 Correct 6225 ms 5448 KB Output is correct
18 Correct 6344 ms 5328 KB Output is correct
19 Execution timed out 9032 ms 4984 KB Time limit exceeded
20 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 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 3054 ms 1656 KB Output is correct
8 Correct 3074 ms 2012 KB Output is correct
9 Correct 3216 ms 3704 KB Output is correct
10 Correct 1822 ms 3676 KB Output is correct
11 Correct 1723 ms 3704 KB Output is correct
12 Correct 4011 ms 3836 KB Output is correct
13 Correct 1715 ms 3708 KB Output is correct
14 Correct 4486 ms 2324 KB Output is correct
15 Correct 4435 ms 2448 KB Output is correct
16 Correct 6358 ms 3880 KB Output is correct
17 Correct 6225 ms 5448 KB Output is correct
18 Correct 6344 ms 5328 KB Output is correct
19 Execution timed out 9032 ms 4984 KB Time limit exceeded
20 Halted 0 ms 0 KB -