oj.uz

답안 #1089215

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1089215 2024-09-16T07:30:47 Z StefanSebez 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
97 / 100
 9000 ms 17232 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];
vector<int>A[N+50];
void Calcblok(int i){
	if(A[i].empty()) return;
	for(int j=A[i].size()-1,k=A[i].size()-1;j>=0;j--){
		while(k>=1 && A[i][j]+L<A[i][k-1]) k--;
		if(A[i][j]+L>=A[i].back()){
			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(A[i].empty()) continue;
		if(A[i][0]<=x && x<=A[i].back()){
			int ind=A[i].size();
			for(int j=0;j<A[i].size();j++) if(A[i][j]==x) ind=j;
			while(ind+1<A[i].size()){swap(A[i][ind],A[i][ind+1]);ind++;}
			A[i].pop_back();
			Calcblok(i);
			break;
		}
	}
}
void Insert(int x){
	for(int i=0;i<=(n-1)/koren;i++){
		if(A[i].empty()) 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].back() || (x<=A[i][0]) || (i==(n-1)/koren)){
			A[i].pb(x);
			int ind=A[i].size();ind--;
			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].pb(b[i]);
	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(A[i].empty()) continue;
		if(x<=A[i].back()){
			int ind=0;
			for(int j=A[i].size()-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();
}
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 Erase(int)':
elephants.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for(int j=0;j<A[i].size();j++) if(A[i][j]==x) ind=j;
      |                ~^~~~~~~~~~~~
elephants.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    while(ind+1<A[i].size()){swap(A[i][ind],A[i][ind+1]);ind++;}
      |          ~~~~~^~~~~~~~~~~~
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].back() || (x<=A[i][0]) || (i==(n-1)/koren)){

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3928 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 3 ms 3932 KB Output is correct
7 Correct 418 ms 5456 KB Output is correct
8 Correct 513 ms 5716 KB Output is correct
9 Correct 1244 ms 6812 KB Output is correct
10 Correct 1284 ms 6828 KB Output is correct
11 Correct 953 ms 6744 KB Output is correct
12 Correct 1395 ms 6744 KB Output is correct
13 Correct 1233 ms 6832 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3928 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 3 ms 3932 KB Output is correct
7 Correct 418 ms 5456 KB Output is correct
8 Correct 513 ms 5716 KB Output is correct
9 Correct 1244 ms 6812 KB Output is correct
10 Correct 1284 ms 6828 KB Output is correct
11 Correct 953 ms 6744 KB Output is correct
12 Correct 1395 ms 6744 KB Output is correct
13 Correct 1233 ms 6832 KB Output is correct
14 Correct 488 ms 5712 KB Output is correct
15 Correct 933 ms 7264 KB Output is correct
16 Correct 2041 ms 8856 KB Output is correct
17 Correct 2869 ms 10004 KB Output is correct
18 Correct 2764 ms 10188 KB Output is correct
19 Correct 2479 ms 10124 KB Output is correct
20 Correct 2849 ms 9864 KB Output is correct
21 Correct 2737 ms 9812 KB Output is correct
22 Correct 2461 ms 9300 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 3928 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 3 ms 3932 KB Output is correct
7 Correct 418 ms 5456 KB Output is correct
8 Correct 513 ms 5716 KB Output is correct
9 Correct 1244 ms 6812 KB Output is correct
10 Correct 1284 ms 6828 KB Output is correct
11 Correct 953 ms 6744 KB Output is correct
12 Correct 1395 ms 6744 KB Output is correct
13 Correct 1233 ms 6832 KB Output is correct
14 Correct 488 ms 5712 KB Output is correct
15 Correct 933 ms 7264 KB Output is correct
16 Correct 2041 ms 8856 KB Output is correct
17 Correct 2869 ms 10004 KB Output is correct
18 Correct 2764 ms 10188 KB Output is correct
19 Correct 2479 ms 10124 KB Output is correct
20 Correct 2849 ms 9864 KB Output is correct
21 Correct 2737 ms 9812 KB Output is correct
22 Correct 2461 ms 9300 KB Output is correct
23 Execution timed out 9005 ms 17232 KB Time limit exceeded
24 Halted 0 ms 0 KB -