oj.uz

Submission #1089275

# Submission time Handle Problem Language Result Execution time Memory
1089275 2024-09-16T09:00:28 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
100 / 100
 2163 ms 16976 KB 
#include "elephants.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")
#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=lower_bound(A[i],A[i]+sajz[i],x)-A[i];
			//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:48:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |   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 348 KB Output is correct
3 Correct 0 ms 344 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 344 KB Output is correct
4 Correct 1 ms 348 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 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 278 ms 2672 KB Output is correct
8 Correct 267 ms 3156 KB Output is correct
9 Correct 262 ms 5200 KB Output is correct
10 Correct 285 ms 5200 KB Output is correct
11 Correct 237 ms 4804 KB Output is correct
12 Correct 385 ms 5200 KB Output is correct
13 Correct 254 ms 4700 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 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 278 ms 2672 KB Output is correct
8 Correct 267 ms 3156 KB Output is correct
9 Correct 262 ms 5200 KB Output is correct
10 Correct 285 ms 5200 KB Output is correct
11 Correct 237 ms 4804 KB Output is correct
12 Correct 385 ms 5200 KB Output is correct
13 Correct 254 ms 4700 KB Output is correct
14 Correct 226 ms 3852 KB Output is correct
15 Correct 342 ms 3932 KB Output is correct
16 Correct 655 ms 5804 KB Output is correct
17 Correct 695 ms 6996 KB Output is correct
18 Correct 697 ms 6992 KB Output is correct
19 Correct 580 ms 7256 KB Output is correct
20 Correct 650 ms 7248 KB Output is correct
21 Correct 602 ms 7064 KB Output is correct
22 Correct 430 ms 6492 KB Output is correct

Subtask #5
3.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 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 278 ms 2672 KB Output is correct
8 Correct 267 ms 3156 KB Output is correct
9 Correct 262 ms 5200 KB Output is correct
10 Correct 285 ms 5200 KB Output is correct
11 Correct 237 ms 4804 KB Output is correct
12 Correct 385 ms 5200 KB Output is correct
13 Correct 254 ms 4700 KB Output is correct
14 Correct 226 ms 3852 KB Output is correct
15 Correct 342 ms 3932 KB Output is correct
16 Correct 655 ms 5804 KB Output is correct
17 Correct 695 ms 6996 KB Output is correct
18 Correct 697 ms 6992 KB Output is correct
19 Correct 580 ms 7256 KB Output is correct
20 Correct 650 ms 7248 KB Output is correct
21 Correct 602 ms 7064 KB Output is correct
22 Correct 430 ms 6492 KB Output is correct
23 Correct 1694 ms 15188 KB Output is correct
24 Correct 1874 ms 15224 KB Output is correct
25 Correct 1427 ms 15300 KB Output is correct
26 Correct 1567 ms 15300 KB Output is correct
27 Correct 2025 ms 15040 KB Output is correct
28 Correct 920 ms 5420 KB Output is correct
29 Correct 916 ms 5196 KB Output is correct
30 Correct 907 ms 5316 KB Output is correct
31 Correct 918 ms 5432 KB Output is correct
32 Correct 1242 ms 14728 KB Output is correct
33 Correct 1027 ms 14064 KB Output is correct
34 Correct 1411 ms 14944 KB Output is correct
35 Correct 951 ms 16976 KB Output is correct
36 Correct 484 ms 14672 KB Output is correct
37 Correct 1672 ms 15976 KB Output is correct
38 Correct 1487 ms 13908 KB Output is correct
39 Correct 1785 ms 15028 KB Output is correct
40 Correct 1439 ms 13964 KB Output is correct
41 Correct 2037 ms 14776 KB Output is correct
42 Correct 2163 ms 14932 KB Output is correct