oj.uz

Submission #1089212

# Submission time Handle Problem Language Result Execution time Memory
1089212 2024-09-16T07:25:18 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
50 / 100
 1462 ms 8364 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(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<=(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==4*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 2 ms 3932 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 2 ms 3928 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3924 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 2 ms 3932 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3924 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 2 ms 3932 KB Output is correct
7 Correct 402 ms 4952 KB Output is correct
8 Correct 540 ms 6236 KB Output is correct
9 Correct 1239 ms 8364 KB Output is correct
10 Correct 1339 ms 8004 KB Output is correct
11 Correct 1200 ms 7944 KB Output is correct
12 Correct 1462 ms 8124 KB Output is correct
13 Correct 1307 ms 7968 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3924 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 2 ms 3932 KB Output is correct
7 Correct 402 ms 4952 KB Output is correct
8 Correct 540 ms 6236 KB Output is correct
9 Correct 1239 ms 8364 KB Output is correct
10 Correct 1339 ms 8004 KB Output is correct
11 Correct 1200 ms 7944 KB Output is correct
12 Correct 1462 ms 8124 KB Output is correct
13 Correct 1307 ms 7968 KB Output is correct
14 Incorrect 171 ms 7156 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3924 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 2 ms 3932 KB Output is correct
7 Correct 402 ms 4952 KB Output is correct
8 Correct 540 ms 6236 KB Output is correct
9 Correct 1239 ms 8364 KB Output is correct
10 Correct 1339 ms 8004 KB Output is correct
11 Correct 1200 ms 7944 KB Output is correct
12 Correct 1462 ms 8124 KB Output is correct
13 Correct 1307 ms 7968 KB Output is correct
14 Incorrect 171 ms 7156 KB Output isn't correct
15 Halted 0 ms 0 KB -