oj.uz

Submission #1089077

# Submission time Handle Problem Language Result Execution time Memory
1089077 2024-09-15T22:17:34 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 18704 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],L,res,nq,dp[600][2500],poslednji[600][2500];
vector<int>A[N+50];
multiset<int>b;
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+4;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<koren;i++) A[i].clear();
	int I=0;
	for(auto i=b.begin();i!=b.end();i++,I++) A[I/koren].pb(*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];
	for(int i=0;i<n;i++) b.insert(a[i]);
	L=L1;
	//for(int i=0;i<koren+50;i++) A[i].reserve(2*koren+10);
	Calc();
}
int update(int qind, int y){
	Erase(a[qind]);
	b.erase(b.find(a[qind]));
	a[qind]=y;
	b.insert(a[qind]);
	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:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for(int j=0;j<A[i].size();j++) if(A[i][j]==x) ind=j;
      |                ~^~~~~~~~~~~~
elephants.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    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 3928 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 3932 KB Output is correct
7 Correct 411 ms 5464 KB Output is correct
8 Correct 506 ms 5980 KB Output is correct
9 Correct 1211 ms 8948 KB Output is correct
10 Correct 1169 ms 8792 KB Output is correct
11 Correct 910 ms 8908 KB Output is correct
12 Correct 1456 ms 8784 KB Output is correct
13 Correct 1220 ms 8796 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 3932 KB Output is correct
7 Correct 411 ms 5464 KB Output is correct
8 Correct 506 ms 5980 KB Output is correct
9 Correct 1211 ms 8948 KB Output is correct
10 Correct 1169 ms 8792 KB Output is correct
11 Correct 910 ms 8908 KB Output is correct
12 Correct 1456 ms 8784 KB Output is correct
13 Correct 1220 ms 8796 KB Output is correct
14 Correct 485 ms 6732 KB Output is correct
15 Correct 879 ms 6848 KB Output is correct
16 Correct 1965 ms 9040 KB Output is correct
17 Correct 2619 ms 10836 KB Output is correct
18 Correct 2698 ms 10980 KB Output is correct
19 Correct 2432 ms 10944 KB Output is correct
20 Correct 2614 ms 10836 KB Output is correct
21 Correct 2606 ms 10836 KB Output is correct
22 Correct 2355 ms 10840 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 3932 KB Output is correct
7 Correct 411 ms 5464 KB Output is correct
8 Correct 506 ms 5980 KB Output is correct
9 Correct 1211 ms 8948 KB Output is correct
10 Correct 1169 ms 8792 KB Output is correct
11 Correct 910 ms 8908 KB Output is correct
12 Correct 1456 ms 8784 KB Output is correct
13 Correct 1220 ms 8796 KB Output is correct
14 Correct 485 ms 6732 KB Output is correct
15 Correct 879 ms 6848 KB Output is correct
16 Correct 1965 ms 9040 KB Output is correct
17 Correct 2619 ms 10836 KB Output is correct
18 Correct 2698 ms 10980 KB Output is correct
19 Correct 2432 ms 10944 KB Output is correct
20 Correct 2614 ms 10836 KB Output is correct
21 Correct 2606 ms 10836 KB Output is correct
22 Correct 2355 ms 10840 KB Output is correct
23 Execution timed out 9059 ms 18704 KB Time limit exceeded
24 Halted 0 ms 0 KB -