oj.uz

Submission #1089277

# Submission time Handle Problem Language Result Execution time Memory
1089277 2024-09-16T09:01:30 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
100 / 100
 2364 ms 14712 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 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 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 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 208 ms 2572 KB Output is correct
8 Correct 214 ms 2896 KB Output is correct
9 Correct 264 ms 4764 KB Output is correct
10 Correct 282 ms 4696 KB Output is correct
11 Correct 288 ms 4444 KB Output is correct
12 Correct 407 ms 4696 KB Output is correct
13 Correct 287 ms 4444 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 348 KB Output is correct
4 Correct 0 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 208 ms 2572 KB Output is correct
8 Correct 214 ms 2896 KB Output is correct
9 Correct 264 ms 4764 KB Output is correct
10 Correct 282 ms 4696 KB Output is correct
11 Correct 288 ms 4444 KB Output is correct
12 Correct 407 ms 4696 KB Output is correct
13 Correct 287 ms 4444 KB Output is correct
14 Correct 250 ms 3512 KB Output is correct
15 Correct 316 ms 3672 KB Output is correct
16 Correct 679 ms 5208 KB Output is correct
17 Correct 706 ms 6592 KB Output is correct
18 Correct 751 ms 6228 KB Output is correct
19 Correct 489 ms 6188 KB Output is correct
20 Correct 758 ms 6176 KB Output is correct
21 Correct 630 ms 6240 KB Output is correct
22 Correct 508 ms 6076 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 348 KB Output is correct
4 Correct 0 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 208 ms 2572 KB Output is correct
8 Correct 214 ms 2896 KB Output is correct
9 Correct 264 ms 4764 KB Output is correct
10 Correct 282 ms 4696 KB Output is correct
11 Correct 288 ms 4444 KB Output is correct
12 Correct 407 ms 4696 KB Output is correct
13 Correct 287 ms 4444 KB Output is correct
14 Correct 250 ms 3512 KB Output is correct
15 Correct 316 ms 3672 KB Output is correct
16 Correct 679 ms 5208 KB Output is correct
17 Correct 706 ms 6592 KB Output is correct
18 Correct 751 ms 6228 KB Output is correct
19 Correct 489 ms 6188 KB Output is correct
20 Correct 758 ms 6176 KB Output is correct
21 Correct 630 ms 6240 KB Output is correct
22 Correct 508 ms 6076 KB Output is correct
23 Correct 1933 ms 13080 KB Output is correct
24 Correct 1954 ms 13088 KB Output is correct
25 Correct 1502 ms 13264 KB Output is correct
26 Correct 1707 ms 13084 KB Output is correct
27 Correct 1883 ms 13084 KB Output is correct
28 Correct 748 ms 4268 KB Output is correct
29 Correct 711 ms 4280 KB Output is correct
30 Correct 750 ms 4264 KB Output is correct
31 Correct 712 ms 4284 KB Output is correct
32 Correct 1377 ms 12624 KB Output is correct
33 Correct 1272 ms 12224 KB Output is correct
34 Correct 1593 ms 12832 KB Output is correct
35 Correct 1225 ms 14712 KB Output is correct
36 Correct 709 ms 12624 KB Output is correct
37 Correct 1957 ms 13884 KB Output is correct
38 Correct 1783 ms 12312 KB Output is correct
39 Correct 1683 ms 12828 KB Output is correct
40 Correct 1547 ms 12116 KB Output is correct
41 Correct 2295 ms 12864 KB Output is correct
42 Correct 2364 ms 12840 KB Output is correct