oj.uz

Submission #1089074

# Submission time Handle Problem Language Result Execution time Memory
1089074 2024-09-15T21:55:18 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 29264 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=390;
int n,a[N],L,res,nq,dp[400][2500],poslednji[400][2500];
vector<int>A[N];
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()) break;
		int l=0,r=inf;
		if(i>=1 && !A[i-1].empty()) 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(){
	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>=koren) {Calc();nq-=koren;}
	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 16220 KB Output is correct
2 Correct 2 ms 16220 KB Output is correct
3 Correct 2 ms 16216 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16220 KB Output is correct
2 Correct 2 ms 16220 KB Output is correct
3 Correct 2 ms 16216 KB Output is correct
4 Correct 2 ms 16216 KB Output is correct
5 Correct 2 ms 16220 KB Output is correct
6 Correct 2 ms 16220 KB Output is correct
7 Correct 425 ms 16904 KB Output is correct
8 Correct 528 ms 17012 KB Output is correct
9 Correct 1200 ms 22616 KB Output is correct
10 Correct 1177 ms 22768 KB Output is correct
11 Correct 845 ms 22764 KB Output is correct
12 Correct 1461 ms 22772 KB Output is correct
13 Correct 1152 ms 22620 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16220 KB Output is correct
2 Correct 2 ms 16220 KB Output is correct
3 Correct 2 ms 16216 KB Output is correct
4 Correct 2 ms 16216 KB Output is correct
5 Correct 2 ms 16220 KB Output is correct
6 Correct 2 ms 16220 KB Output is correct
7 Correct 425 ms 16904 KB Output is correct
8 Correct 528 ms 17012 KB Output is correct
9 Correct 1200 ms 22616 KB Output is correct
10 Correct 1177 ms 22768 KB Output is correct
11 Correct 845 ms 22764 KB Output is correct
12 Correct 1461 ms 22772 KB Output is correct
13 Correct 1152 ms 22620 KB Output is correct
14 Correct 482 ms 17140 KB Output is correct
15 Correct 901 ms 17244 KB Output is correct
16 Correct 2111 ms 22768 KB Output is correct
17 Correct 2758 ms 23708 KB Output is correct
18 Correct 2929 ms 23704 KB Output is correct
19 Correct 2488 ms 23644 KB Output is correct
20 Correct 2786 ms 23644 KB Output is correct
21 Correct 2780 ms 23632 KB Output is correct
22 Correct 2373 ms 23660 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16220 KB Output is correct
2 Correct 2 ms 16220 KB Output is correct
3 Correct 2 ms 16216 KB Output is correct
4 Correct 2 ms 16216 KB Output is correct
5 Correct 2 ms 16220 KB Output is correct
6 Correct 2 ms 16220 KB Output is correct
7 Correct 425 ms 16904 KB Output is correct
8 Correct 528 ms 17012 KB Output is correct
9 Correct 1200 ms 22616 KB Output is correct
10 Correct 1177 ms 22768 KB Output is correct
11 Correct 845 ms 22764 KB Output is correct
12 Correct 1461 ms 22772 KB Output is correct
13 Correct 1152 ms 22620 KB Output is correct
14 Correct 482 ms 17140 KB Output is correct
15 Correct 901 ms 17244 KB Output is correct
16 Correct 2111 ms 22768 KB Output is correct
17 Correct 2758 ms 23708 KB Output is correct
18 Correct 2929 ms 23704 KB Output is correct
19 Correct 2488 ms 23644 KB Output is correct
20 Correct 2786 ms 23644 KB Output is correct
21 Correct 2780 ms 23632 KB Output is correct
22 Correct 2373 ms 23660 KB Output is correct
23 Execution timed out 9043 ms 29264 KB Time limit exceeded
24 Halted 0 ms 0 KB -