oj.uz

Submission #1089249

# Submission time Handle Problem Language Result Execution time Memory
1089249 2024-09-16T08:13:25 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
50 / 100
 1543 ms 5212 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][2500],poslednji[600][2500];
int A[600][2500],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,j=i;
			while(l<=r){
				int mid=l+r>>1;
				if(x<=A[mid][sajz[mid]-1]){j=mid,r=mid-1;}
				else l=mid+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;
		}
	}
	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 0 ms 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 413 ms 2668 KB Output is correct
8 Correct 541 ms 3152 KB Output is correct
9 Correct 1202 ms 5212 KB Output is correct
10 Correct 1218 ms 5080 KB Output is correct
11 Correct 1090 ms 5020 KB Output is correct
12 Correct 1543 ms 5192 KB Output is correct
13 Correct 1193 ms 4696 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 413 ms 2668 KB Output is correct
8 Correct 541 ms 3152 KB Output is correct
9 Correct 1202 ms 5212 KB Output is correct
10 Correct 1218 ms 5080 KB Output is correct
11 Correct 1090 ms 5020 KB Output is correct
12 Correct 1543 ms 5192 KB Output is correct
13 Correct 1193 ms 4696 KB Output is correct
14 Incorrect 133 ms 3676 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 413 ms 2668 KB Output is correct
8 Correct 541 ms 3152 KB Output is correct
9 Correct 1202 ms 5212 KB Output is correct
10 Correct 1218 ms 5080 KB Output is correct
11 Correct 1090 ms 5020 KB Output is correct
12 Correct 1543 ms 5192 KB Output is correct
13 Correct 1193 ms 4696 KB Output is correct
14 Incorrect 133 ms 3676 KB Output isn't correct
15 Halted 0 ms 0 KB -