oj.uz

Submission #1089055

# Submission time Handle Problem Language Result Execution time Memory
1089055 2024-09-15T21:24:20 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 24660 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],L,res,nq,dp[1500][1500],poslednji[1500][1500];
vector<int>A[N];
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<koren+50;i++){
		if(A[i].empty()) break;
		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<koren+50;i++){
		if(A[i].empty()) break;
		int l=0,r=inf;
		if(i>=1) l=A[i-1].back();
		if(!A[i+1].empty()) r=A[i+1][0];
		if(l<=x && x<=r){
			A[i].pb(x);
			int ind=A[i].size()-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 b[n+10];for(int i=0;i<n;i++) b[i]=a[i];
	sort(b,b+n);
	for(int i=0;i<=koren+50;i++) A[i].clear();
	for(int i=0;i<n;i++) A[i/koren].pb(b[i]);
	for(int i=0;i<koren+50;i++) Calcblok(i);
}
void init(int N1, int L1, int X[]){
	n = N1;
	for(int i=0;i<n;i++) a[i]=X[i];
	L=L1;
	Calc();
	for(int i=0;i<50;i++){
		if(A[i].empty())break;
		/*for(auto j:A[i]) printf("%i ",j);printf("\n");
		for(int j=0;j<A[i].size();j++) printf("%i ",dp[i][j]);printf("\n");
		for(int j=0;j<A[i].size();j++) printf("%i ",poslednji[i][j]);printf("\n");*/
	}
}
int update(int qind, int y){
	Erase(a[qind]);
	a[qind]=y;
	Insert(a[qind]);
	nq++;
	if(nq>=koren) {Calc();nq-=koren;}
	/*printf("\n");
	for(int i=0;i<koren+50;i++){
		if(A[i].empty())break;
		for(auto j:A[i]) printf("%i ",j);printf("\n");
	}
	printf("\n");*/
	int res=0;
	int x=A[0][0];
	//printf("da\n");
	for(int i=0;i<koren+50;i++){
		//printf("%i ",x);
		if(A[i].empty()) break;
		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;
		}
	}
	//printf("\n");
	return res;
}

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++;}
      |          ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14984 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14968 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14984 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14968 KB Output is correct
7 Correct 439 ms 18020 KB Output is correct
8 Correct 525 ms 18008 KB Output is correct
9 Correct 1244 ms 19032 KB Output is correct
10 Correct 1301 ms 18812 KB Output is correct
11 Correct 1054 ms 18520 KB Output is correct
12 Correct 1521 ms 18668 KB Output is correct
13 Correct 1356 ms 18524 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14984 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14968 KB Output is correct
7 Correct 439 ms 18020 KB Output is correct
8 Correct 525 ms 18008 KB Output is correct
9 Correct 1244 ms 19032 KB Output is correct
10 Correct 1301 ms 18812 KB Output is correct
11 Correct 1054 ms 18520 KB Output is correct
12 Correct 1521 ms 18668 KB Output is correct
13 Correct 1356 ms 18524 KB Output is correct
14 Correct 515 ms 18524 KB Output is correct
15 Correct 959 ms 18512 KB Output is correct
16 Correct 2305 ms 19280 KB Output is correct
17 Correct 3041 ms 18704 KB Output is correct
18 Correct 3051 ms 21668 KB Output is correct
19 Correct 2583 ms 21864 KB Output is correct
20 Correct 3102 ms 18516 KB Output is correct
21 Correct 3120 ms 18524 KB Output is correct
22 Correct 2551 ms 19508 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14984 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14968 KB Output is correct
7 Correct 439 ms 18020 KB Output is correct
8 Correct 525 ms 18008 KB Output is correct
9 Correct 1244 ms 19032 KB Output is correct
10 Correct 1301 ms 18812 KB Output is correct
11 Correct 1054 ms 18520 KB Output is correct
12 Correct 1521 ms 18668 KB Output is correct
13 Correct 1356 ms 18524 KB Output is correct
14 Correct 515 ms 18524 KB Output is correct
15 Correct 959 ms 18512 KB Output is correct
16 Correct 2305 ms 19280 KB Output is correct
17 Correct 3041 ms 18704 KB Output is correct
18 Correct 3051 ms 21668 KB Output is correct
19 Correct 2583 ms 21864 KB Output is correct
20 Correct 3102 ms 18516 KB Output is correct
21 Correct 3120 ms 18524 KB Output is correct
22 Correct 2551 ms 19508 KB Output is correct
23 Execution timed out 9056 ms 24660 KB Time limit exceeded
24 Halted 0 ms 0 KB -