oj.uz

답안 #1089224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1089224 2024-09-16T07:42:38 Z StefanSebez 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
97 / 100
 9000 ms 15124 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;i++) b[i]=a[i];
	sort(b,b+n);
	//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;
	int x=A[0][0];
	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];
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 444 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 444 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 458 ms 2972 KB Output is correct
8 Correct 550 ms 3156 KB Output is correct
9 Correct 1183 ms 5292 KB Output is correct
10 Correct 1270 ms 5080 KB Output is correct
11 Correct 1020 ms 4956 KB Output is correct
12 Correct 1445 ms 5452 KB Output is correct
13 Correct 1222 ms 4696 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 444 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 458 ms 2972 KB Output is correct
8 Correct 550 ms 3156 KB Output is correct
9 Correct 1183 ms 5292 KB Output is correct
10 Correct 1270 ms 5080 KB Output is correct
11 Correct 1020 ms 4956 KB Output is correct
12 Correct 1445 ms 5452 KB Output is correct
13 Correct 1222 ms 4696 KB Output is correct
14 Correct 507 ms 3912 KB Output is correct
15 Correct 935 ms 3988 KB Output is correct
16 Correct 2166 ms 5712 KB Output is correct
17 Correct 2939 ms 7084 KB Output is correct
18 Correct 2863 ms 6996 KB Output is correct
19 Correct 2511 ms 7004 KB Output is correct
20 Correct 2913 ms 7088 KB Output is correct
21 Correct 2875 ms 7320 KB Output is correct
22 Correct 2355 ms 6492 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 444 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 458 ms 2972 KB Output is correct
8 Correct 550 ms 3156 KB Output is correct
9 Correct 1183 ms 5292 KB Output is correct
10 Correct 1270 ms 5080 KB Output is correct
11 Correct 1020 ms 4956 KB Output is correct
12 Correct 1445 ms 5452 KB Output is correct
13 Correct 1222 ms 4696 KB Output is correct
14 Correct 507 ms 3912 KB Output is correct
15 Correct 935 ms 3988 KB Output is correct
16 Correct 2166 ms 5712 KB Output is correct
17 Correct 2939 ms 7084 KB Output is correct
18 Correct 2863 ms 6996 KB Output is correct
19 Correct 2511 ms 7004 KB Output is correct
20 Correct 2913 ms 7088 KB Output is correct
21 Correct 2875 ms 7320 KB Output is correct
22 Correct 2355 ms 6492 KB Output is correct
23 Execution timed out 9082 ms 15124 KB Time limit exceeded
24 Halted 0 ms 0 KB -