oj.uz

Submission #1089059

# Submission time Handle Problem Language Result Execution time Memory
1089059 2024-09-15T21:31:18 Z StefanSebez Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 28788 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[1500][1500],poslednji[1500][1500];
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()) break;
		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) 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()) break;
		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;
	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 14940 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 1 ms 12892 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 1 ms 12892 KB Output is correct
7 Correct 401 ms 11920 KB Output is correct
8 Correct 547 ms 17920 KB Output is correct
9 Correct 1219 ms 19544 KB Output is correct
10 Correct 1108 ms 19616 KB Output is correct
11 Correct 814 ms 19548 KB Output is correct
12 Correct 1354 ms 19624 KB Output is correct
13 Correct 1150 ms 19624 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 1 ms 12892 KB Output is correct
7 Correct 401 ms 11920 KB Output is correct
8 Correct 547 ms 17920 KB Output is correct
9 Correct 1219 ms 19544 KB Output is correct
10 Correct 1108 ms 19616 KB Output is correct
11 Correct 814 ms 19548 KB Output is correct
12 Correct 1354 ms 19624 KB Output is correct
13 Correct 1150 ms 19624 KB Output is correct
14 Correct 480 ms 17748 KB Output is correct
15 Correct 883 ms 18012 KB Output is correct
16 Correct 2113 ms 19616 KB Output is correct
17 Correct 2690 ms 22712 KB Output is correct
18 Correct 2856 ms 22716 KB Output is correct
19 Correct 2374 ms 22616 KB Output is correct
20 Correct 2846 ms 22616 KB Output is correct
21 Correct 2806 ms 22608 KB Output is correct
22 Correct 2340 ms 22608 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 1 ms 12892 KB Output is correct
7 Correct 401 ms 11920 KB Output is correct
8 Correct 547 ms 17920 KB Output is correct
9 Correct 1219 ms 19544 KB Output is correct
10 Correct 1108 ms 19616 KB Output is correct
11 Correct 814 ms 19548 KB Output is correct
12 Correct 1354 ms 19624 KB Output is correct
13 Correct 1150 ms 19624 KB Output is correct
14 Correct 480 ms 17748 KB Output is correct
15 Correct 883 ms 18012 KB Output is correct
16 Correct 2113 ms 19616 KB Output is correct
17 Correct 2690 ms 22712 KB Output is correct
18 Correct 2856 ms 22716 KB Output is correct
19 Correct 2374 ms 22616 KB Output is correct
20 Correct 2846 ms 22616 KB Output is correct
21 Correct 2806 ms 22608 KB Output is correct
22 Correct 2340 ms 22608 KB Output is correct
23 Execution timed out 9055 ms 28788 KB Time limit exceeded
24 Halted 0 ms 0 KB -