oj.uz

Submission #1089078

# Submission time Handle Problem Language Result Execution time Memory
1089078 2024-09-15T22:21:23 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 13772 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 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 3 ms 5720 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 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 3 ms 5720 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 410 ms 6924 KB Output is correct
8 Correct 513 ms 7104 KB Output is correct
9 Correct 1188 ms 8284 KB Output is correct
10 Correct 1331 ms 8280 KB Output is correct
11 Correct 1004 ms 8456 KB Output is correct
12 Correct 1509 ms 8256 KB Output is correct
13 Correct 1242 ms 8464 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 3 ms 5720 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 410 ms 6924 KB Output is correct
8 Correct 513 ms 7104 KB Output is correct
9 Correct 1188 ms 8284 KB Output is correct
10 Correct 1331 ms 8280 KB Output is correct
11 Correct 1004 ms 8456 KB Output is correct
12 Correct 1509 ms 8256 KB Output is correct
13 Correct 1242 ms 8464 KB Output is correct
14 Correct 550 ms 7368 KB Output is correct
15 Correct 893 ms 7516 KB Output is correct
16 Correct 2179 ms 8608 KB Output is correct
17 Correct 2807 ms 9520 KB Output is correct
18 Correct 3041 ms 9308 KB Output is correct
19 Correct 2555 ms 9520 KB Output is correct
20 Correct 2855 ms 9536 KB Output is correct
21 Correct 2909 ms 9296 KB Output is correct
22 Correct 2512 ms 9516 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 3 ms 5720 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 410 ms 6924 KB Output is correct
8 Correct 513 ms 7104 KB Output is correct
9 Correct 1188 ms 8284 KB Output is correct
10 Correct 1331 ms 8280 KB Output is correct
11 Correct 1004 ms 8456 KB Output is correct
12 Correct 1509 ms 8256 KB Output is correct
13 Correct 1242 ms 8464 KB Output is correct
14 Correct 550 ms 7368 KB Output is correct
15 Correct 893 ms 7516 KB Output is correct
16 Correct 2179 ms 8608 KB Output is correct
17 Correct 2807 ms 9520 KB Output is correct
18 Correct 3041 ms 9308 KB Output is correct
19 Correct 2555 ms 9520 KB Output is correct
20 Correct 2855 ms 9536 KB Output is correct
21 Correct 2909 ms 9296 KB Output is correct
22 Correct 2512 ms 9516 KB Output is correct
23 Execution timed out 9056 ms 13772 KB Time limit exceeded
24 Halted 0 ms 0 KB -