oj.uz

Submission #1089079

# Submission time Handle Problem Language Result Execution time Memory
1089079 2024-09-15T22:24:47 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 13648 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<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<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+3;j++) if(!A[j].empty()){r=A[j][0];break;}
		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(){
	for(int i=0;i<n;i++) b[i]=a[i];
	sort(b,b+n);
	for(int i=0;i<koren;i++) A[i].clear();
	for(int i=0;i<n;i++) A[i/koren].pb(b[i]);
	for(int i=0;i<koren;i++) Calcblok(i);
}
int Resi(){
	int res=0;
	int x=A[0][0];
	for(int i=0;i<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++;}
      |          ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 5724 KB Output is correct
4 Correct 3 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 5724 KB Output is correct
4 Correct 3 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 414 ms 6912 KB Output is correct
8 Correct 519 ms 7000 KB Output is correct
9 Correct 1174 ms 8280 KB Output is correct
10 Correct 1280 ms 8456 KB Output is correct
11 Correct 953 ms 8280 KB Output is correct
12 Correct 1468 ms 8280 KB Output is correct
13 Correct 1345 ms 8456 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 5724 KB Output is correct
4 Correct 3 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 414 ms 6912 KB Output is correct
8 Correct 519 ms 7000 KB Output is correct
9 Correct 1174 ms 8280 KB Output is correct
10 Correct 1280 ms 8456 KB Output is correct
11 Correct 953 ms 8280 KB Output is correct
12 Correct 1468 ms 8280 KB Output is correct
13 Correct 1345 ms 8456 KB Output is correct
14 Correct 487 ms 7364 KB Output is correct
15 Correct 891 ms 7504 KB Output is correct
16 Correct 2216 ms 8692 KB Output is correct
17 Correct 2966 ms 9528 KB Output is correct
18 Correct 2872 ms 9516 KB Output is correct
19 Correct 2560 ms 9304 KB Output is correct
20 Correct 2816 ms 9300 KB Output is correct
21 Correct 2823 ms 9556 KB Output is correct
22 Correct 2538 ms 9516 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 5724 KB Output is correct
4 Correct 3 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 414 ms 6912 KB Output is correct
8 Correct 519 ms 7000 KB Output is correct
9 Correct 1174 ms 8280 KB Output is correct
10 Correct 1280 ms 8456 KB Output is correct
11 Correct 953 ms 8280 KB Output is correct
12 Correct 1468 ms 8280 KB Output is correct
13 Correct 1345 ms 8456 KB Output is correct
14 Correct 487 ms 7364 KB Output is correct
15 Correct 891 ms 7504 KB Output is correct
16 Correct 2216 ms 8692 KB Output is correct
17 Correct 2966 ms 9528 KB Output is correct
18 Correct 2872 ms 9516 KB Output is correct
19 Correct 2560 ms 9304 KB Output is correct
20 Correct 2816 ms 9300 KB Output is correct
21 Correct 2823 ms 9556 KB Output is correct
22 Correct 2538 ms 9516 KB Output is correct
23 Execution timed out 9038 ms 13648 KB Time limit exceeded
24 Halted 0 ms 0 KB -