oj.uz

Submission #1089075

# Submission time Handle Problem Language Result Execution time Memory
1089075 2024-09-15T21:57:34 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 29784 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=430;
int n,a[N],L,res,nq,dp[500][2500],poslednji[500][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 16476 KB Output is correct
2 Correct 2 ms 16476 KB Output is correct
3 Correct 2 ms 16624 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16476 KB Output is correct
2 Correct 2 ms 16476 KB Output is correct
3 Correct 2 ms 16624 KB Output is correct
4 Correct 3 ms 16476 KB Output is correct
5 Correct 3 ms 16476 KB Output is correct
6 Correct 2 ms 16476 KB Output is correct
7 Correct 473 ms 17176 KB Output is correct
8 Correct 541 ms 17240 KB Output is correct
9 Correct 1226 ms 20992 KB Output is correct
10 Correct 1310 ms 20996 KB Output is correct
11 Correct 857 ms 20816 KB Output is correct
12 Correct 1396 ms 21096 KB Output is correct
13 Correct 1221 ms 20828 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16476 KB Output is correct
2 Correct 2 ms 16476 KB Output is correct
3 Correct 2 ms 16624 KB Output is correct
4 Correct 3 ms 16476 KB Output is correct
5 Correct 3 ms 16476 KB Output is correct
6 Correct 2 ms 16476 KB Output is correct
7 Correct 473 ms 17176 KB Output is correct
8 Correct 541 ms 17240 KB Output is correct
9 Correct 1226 ms 20992 KB Output is correct
10 Correct 1310 ms 20996 KB Output is correct
11 Correct 857 ms 20816 KB Output is correct
12 Correct 1396 ms 21096 KB Output is correct
13 Correct 1221 ms 20828 KB Output is correct
14 Correct 538 ms 17420 KB Output is correct
15 Correct 919 ms 17688 KB Output is correct
16 Correct 2319 ms 20996 KB Output is correct
17 Correct 2723 ms 21936 KB Output is correct
18 Correct 2861 ms 21928 KB Output is correct
19 Correct 2388 ms 21840 KB Output is correct
20 Correct 2800 ms 21932 KB Output is correct
21 Correct 2845 ms 21940 KB Output is correct
22 Correct 2473 ms 21936 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16476 KB Output is correct
2 Correct 2 ms 16476 KB Output is correct
3 Correct 2 ms 16624 KB Output is correct
4 Correct 3 ms 16476 KB Output is correct
5 Correct 3 ms 16476 KB Output is correct
6 Correct 2 ms 16476 KB Output is correct
7 Correct 473 ms 17176 KB Output is correct
8 Correct 541 ms 17240 KB Output is correct
9 Correct 1226 ms 20992 KB Output is correct
10 Correct 1310 ms 20996 KB Output is correct
11 Correct 857 ms 20816 KB Output is correct
12 Correct 1396 ms 21096 KB Output is correct
13 Correct 1221 ms 20828 KB Output is correct
14 Correct 538 ms 17420 KB Output is correct
15 Correct 919 ms 17688 KB Output is correct
16 Correct 2319 ms 20996 KB Output is correct
17 Correct 2723 ms 21936 KB Output is correct
18 Correct 2861 ms 21928 KB Output is correct
19 Correct 2388 ms 21840 KB Output is correct
20 Correct 2800 ms 21932 KB Output is correct
21 Correct 2845 ms 21940 KB Output is correct
22 Correct 2473 ms 21936 KB Output is correct
23 Execution timed out 9052 ms 29784 KB Time limit exceeded
24 Halted 0 ms 0 KB -