oj.uz

Submission #1089254

# Submission time Handle Problem Language Result Execution time Memory
1089254 2024-09-16T08:18:05 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 13344 KB 
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=150050,inf=1e9;
int koren=400;
int n,a[N+50],b[N+50],L,res,nq,dp[600][1000],poslednji[600][1000];
int A[600][1000],sajz[600];
void Calcblok(int i){
	if(sajz[i]==0) return;
	for(int j=sajz[i]-1,k=sajz[i]-1;j>=0;j--){
		while(k>=1 && A[i][j]+L<A[i][k-1]) k--;
		if(A[i][j]+L>=A[i][sajz[i]-1]){
			dp[i][j]=1;
			poslednji[i][j]=j;
		}
		else{
			dp[i][j]=1+dp[i][k];
			poslednji[i][j]=poslednji[i][k];
		}
	}
}
void Erase(int x){
	for(int i=0;i<=(n-1)/koren;i++){
		if(sajz[i]==0) continue;
		if(A[i][0]<=x && x<=A[i][sajz[i]-1]){
			int ind=sajz[i];
			for(int j=0;j<sajz[i];j++) if(A[i][j]==x) ind=j;
			while(ind+1<sajz[i]){swap(A[i][ind],A[i][ind+1]);ind++;}
			sajz[i]--;
			Calcblok(i);
			break;
		}
	}
}
void Insert(int x){
	for(int i=0;i<=(n-1)/koren;i++){
		if(sajz[i]==0) continue;
		/*int l=0,r=inf;
		for(int j=i-1;j>=0;j--) if(!A[j].empty()){l=A[j].back();break;}
		for(int j=i+1;j<=i+5;j++) if(!A[j].empty()){r=A[j][0];break;}*/
		if(A[i][0]<=x && x<=A[i][sajz[i]-1] || (x<=A[i][0]) || (i==(n-1)/koren)){
			sajz[i]++;
			A[i][sajz[i]-1]=x;
			int ind=sajz[i]-1;
			while(ind>=1 && A[i][ind]<A[i][ind-1]){swap(A[i][ind],A[i][ind-1]);ind--;}
			Calcblok(i);
			break;
		}
	}
}
void Calc(){
	int ct=-1;
	for(int i=0;i<=(n-1)/koren;i++){
		for(int j=0;j<sajz[i];j++) b[++ct]=A[i][j];
	}
	for(int i=0;i<n;i++){
		A[i/koren][i%koren]=b[i];
		sajz[i/koren]=i%koren+1;
	}
	for(int i=0;i<=(n-1)/koren;i++) Calcblok(i);
}
int Resi(){
	int res=0,x=-1;
	for(int i=0;i<=(n-1)/koren;i++){
		if(sajz[i]==0) continue;
		if(x<=A[i][sajz[i]-1]){
			int ind=0;
			for(int j=sajz[i]-1;j>=0;j--) if(A[i][j]>=x) ind=j;
			res+=dp[i][ind];
			x=A[i][poslednji[i][ind]]+L+1;
		}
		else{
			int l=i,r=(n-1)/koren-1,j=-1;
			while(l<=r){
				int mid=l+r>>1;
				if(x<=A[mid][sajz[mid]-1]){j=mid,r=mid-1;}
				else l=mid+1;
			}
			if(j!=-1){
				i=j;
				int ind=0;
				for(int j=sajz[i]-1;j>=0;j--) if(A[i][j]>=x) ind=j;
				res+=dp[i][ind];
				x=A[i][poslednji[i][ind]]+L+1;
			}
			else j=(n-1)/koren-1;
		}
	}
	return res;
}
void init(int N1, int L1, int X[]){
	n = N1;
	for(int i=0;i<n;i++) a[i]=X[i];
	for(int i=0;i<n;i++) b[i]=a[i];
	sort(b,b+n);
	for(int i=0;i<n;i++){
		A[i/koren][i%koren]=b[i];
		sajz[i/koren]=i%koren+1;
	}
	L=L1;
	//for(int i=0;i<koren+50;i++) A[i].reserve(3*koren+10);
	Calc();
	//for(int i=0;i<=(n-1)/koren;i++) printf("%i ",sajz[i]);
}
int update(int qind, int y){
	Erase(a[qind]);
	a[qind]=y;
	Insert(a[qind]);
	nq++;
	if(nq==koren-5) {Calc();nq=0;}
	return Resi();
}

Compilation message

elephants.cpp: In function 'void Insert(int)':
elephants.cpp:46:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   46 |   if(A[i][0]<=x && x<=A[i][sajz[i]-1] || (x<=A[i][0]) || (i==(n-1)/koren)){
      |      ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int Resi()':
elephants.cpp:80:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 419 ms 2480 KB Output is correct
8 Correct 600 ms 2784 KB Output is correct
9 Correct 1209 ms 4672 KB Output is correct
10 Correct 1194 ms 4448 KB Output is correct
11 Correct 898 ms 4384 KB Output is correct
12 Correct 1420 ms 4548 KB Output is correct
13 Correct 1227 ms 4248 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 419 ms 2480 KB Output is correct
8 Correct 600 ms 2784 KB Output is correct
9 Correct 1209 ms 4672 KB Output is correct
10 Correct 1194 ms 4448 KB Output is correct
11 Correct 898 ms 4384 KB Output is correct
12 Correct 1420 ms 4548 KB Output is correct
13 Correct 1227 ms 4248 KB Output is correct
14 Correct 454 ms 3512 KB Output is correct
15 Correct 923 ms 3672 KB Output is correct
16 Correct 2028 ms 5156 KB Output is correct
17 Correct 2701 ms 6204 KB Output is correct
18 Correct 2747 ms 6132 KB Output is correct
19 Correct 2428 ms 6336 KB Output is correct
20 Correct 2721 ms 5968 KB Output is correct
21 Correct 2655 ms 5976 KB Output is correct
22 Correct 2411 ms 5944 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 419 ms 2480 KB Output is correct
8 Correct 600 ms 2784 KB Output is correct
9 Correct 1209 ms 4672 KB Output is correct
10 Correct 1194 ms 4448 KB Output is correct
11 Correct 898 ms 4384 KB Output is correct
12 Correct 1420 ms 4548 KB Output is correct
13 Correct 1227 ms 4248 KB Output is correct
14 Correct 454 ms 3512 KB Output is correct
15 Correct 923 ms 3672 KB Output is correct
16 Correct 2028 ms 5156 KB Output is correct
17 Correct 2701 ms 6204 KB Output is correct
18 Correct 2747 ms 6132 KB Output is correct
19 Correct 2428 ms 6336 KB Output is correct
20 Correct 2721 ms 5968 KB Output is correct
21 Correct 2655 ms 5976 KB Output is correct
22 Correct 2411 ms 5944 KB Output is correct
23 Execution timed out 9033 ms 13344 KB Time limit exceeded
24 Halted 0 ms 0 KB -