oj.uz

Submission #1089231

# Submission time Handle Problem Language Result Execution time Memory
1089231 2024-09-16T07:50:51 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 15280 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(){
	//for(int i=0;i<=(n-1)/koren;i++) A[i].clear();
	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;
		}
	}
	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);
	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]);
	for(int i=n-1;i>=0;i--){
		if(b[i]==a[qind]){
			for(int j=i+1;j<n;j++) b[j-1]=b[j];
			break;
		}
	}
	a[qind]=y;
	Insert(a[qind]);
	b[n-1]=a[qind];
	for(int j=n-1;j>=1;j--){
		if(b[j-1]>b[j]) swap(b[j-1],b[j]);
		else break;
	}
	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)){
      |      ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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 452 KB Output is correct
3 Correct 0 ms 448 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 452 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 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 452 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 767 ms 2652 KB Output is correct
8 Correct 963 ms 3284 KB Output is correct
9 Correct 2662 ms 5204 KB Output is correct
10 Correct 2515 ms 5084 KB Output is correct
11 Correct 1978 ms 5020 KB Output is correct
12 Correct 2274 ms 5188 KB Output is correct
13 Correct 2255 ms 4872 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 767 ms 2652 KB Output is correct
8 Correct 963 ms 3284 KB Output is correct
9 Correct 2662 ms 5204 KB Output is correct
10 Correct 2515 ms 5084 KB Output is correct
11 Correct 1978 ms 5020 KB Output is correct
12 Correct 2274 ms 5188 KB Output is correct
13 Correct 2255 ms 4872 KB Output is correct
14 Correct 953 ms 3816 KB Output is correct
15 Correct 1753 ms 3972 KB Output is correct
16 Correct 3904 ms 5972 KB Output is correct
17 Correct 4880 ms 7104 KB Output is correct
18 Correct 4862 ms 6992 KB Output is correct
19 Correct 5576 ms 6996 KB Output is correct
20 Correct 5001 ms 7080 KB Output is correct
21 Correct 4525 ms 7068 KB Output is correct
22 Correct 4296 ms 6492 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 767 ms 2652 KB Output is correct
8 Correct 963 ms 3284 KB Output is correct
9 Correct 2662 ms 5204 KB Output is correct
10 Correct 2515 ms 5084 KB Output is correct
11 Correct 1978 ms 5020 KB Output is correct
12 Correct 2274 ms 5188 KB Output is correct
13 Correct 2255 ms 4872 KB Output is correct
14 Correct 953 ms 3816 KB Output is correct
15 Correct 1753 ms 3972 KB Output is correct
16 Correct 3904 ms 5972 KB Output is correct
17 Correct 4880 ms 7104 KB Output is correct
18 Correct 4862 ms 6992 KB Output is correct
19 Correct 5576 ms 6996 KB Output is correct
20 Correct 5001 ms 7080 KB Output is correct
21 Correct 4525 ms 7068 KB Output is correct
22 Correct 4296 ms 6492 KB Output is correct
23 Execution timed out 9050 ms 15280 KB Time limit exceeded
24 Halted 0 ms 0 KB -