oj.uz

Submission #1089244

# Submission time Handle Problem Language Result Execution time Memory
1089244 2024-09-16T08:06:14 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(){
	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;
		}
	}
	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==2*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 1 ms 348 KB Output is correct
2 Correct 1 ms 444 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 348 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 448 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 1 ms 348 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 481 ms 2900 KB Output is correct
8 Correct 525 ms 3028 KB Output is correct
9 Correct 1240 ms 5204 KB Output is correct
10 Correct 1230 ms 5080 KB Output is correct
11 Correct 955 ms 5024 KB Output is correct
12 Correct 1319 ms 5208 KB Output is correct
13 Correct 1138 ms 4888 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 481 ms 2900 KB Output is correct
8 Correct 525 ms 3028 KB Output is correct
9 Correct 1240 ms 5204 KB Output is correct
10 Correct 1230 ms 5080 KB Output is correct
11 Correct 955 ms 5024 KB Output is correct
12 Correct 1319 ms 5208 KB Output is correct
13 Correct 1138 ms 4888 KB Output is correct
14 Correct 502 ms 3928 KB Output is correct
15 Correct 890 ms 4180 KB Output is correct
16 Correct 2009 ms 5804 KB Output is correct
17 Correct 2801 ms 7084 KB Output is correct
18 Correct 2765 ms 7024 KB Output is correct
19 Correct 2423 ms 7208 KB Output is correct
20 Correct 2676 ms 7088 KB Output is correct
21 Correct 2564 ms 6940 KB Output is correct
22 Correct 2430 ms 6648 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 481 ms 2900 KB Output is correct
8 Correct 525 ms 3028 KB Output is correct
9 Correct 1240 ms 5204 KB Output is correct
10 Correct 1230 ms 5080 KB Output is correct
11 Correct 955 ms 5024 KB Output is correct
12 Correct 1319 ms 5208 KB Output is correct
13 Correct 1138 ms 4888 KB Output is correct
14 Correct 502 ms 3928 KB Output is correct
15 Correct 890 ms 4180 KB Output is correct
16 Correct 2009 ms 5804 KB Output is correct
17 Correct 2801 ms 7084 KB Output is correct
18 Correct 2765 ms 7024 KB Output is correct
19 Correct 2423 ms 7208 KB Output is correct
20 Correct 2676 ms 7088 KB Output is correct
21 Correct 2564 ms 6940 KB Output is correct
22 Correct 2430 ms 6648 KB Output is correct
23 Execution timed out 9043 ms 15280 KB Time limit exceeded
24 Halted 0 ms 0 KB -