oj.uz

Submission #96739

# Submission time Handle Problem Language Result Execution time Memory
96739 2019-02-11T15:35:47 Z jangwonyoung Dancing Elephants (IOI11_elephants) C++14
50 / 100
 648 ms 3908 KB 
#include "elephants.h"
#include<iostream>
#include<queue>
using namespace std;
const int bs=400;
int bc;
int x[150000];
int n,l;
vector<int>bl[400];
vector<int>dp[400];
vector<int>en[400];
int z[150000];
int rnd=0;

void yena(int pos){
	dp[pos].resize(bl[pos].size()); dp[pos].shrink_to_fit();
	en[pos].resize(bl[pos].size()); en[pos].shrink_to_fit();
	if(bl[pos].empty()) return;
	int ptr=bl[pos].size();
	for(int i=(int)bl[pos].size()-1; i>=0 ;i--){
		while(ptr!=0 && bl[pos][ptr-1]>l+bl[pos][i]) --ptr;
		if(ptr==bl[pos].size()) dp[pos][i]=1,en[pos][i]=bl[pos][i]+l+1;
		else dp[pos][i]=1+dp[pos][ptr],en[pos][i]=en[pos][ptr];
	}
}
int sakura(){
	int ans=0,cur=0;
	for(int i=0; i<bc ;i++){
		if(bl[i].empty() || bl[i].back()<cur) continue;
		int pos=lower_bound(bl[i].begin(),bl[i].end(),cur)-bl[i].begin();
		ans+=dp[i][pos],cur=en[i][pos];
	}
	return ans;
}
void iu(){
	int tzuyu=0;
	for(int i=0; i<bc ;i++){
		for(auto cur:bl[i]) z[tzuyu++]=cur;
		bl[i].clear();
	}
	for(int i=0; i<n ;i++) bl[i/bs].push_back(z[i]);
	for(int i=0; i<bc ;i++){
		bl[i].shrink_to_fit();
		yena(i);
	}
}
int find(int x){
	for(int i=0; i<bc ;i++) if(!bl[i].empty() && bl[i].back()>=x) return i;
	return bc-1;
}
void init(int N, int L, int X[]){
	n=N;l=L;
	bc=(n-1)/bs+1;
	for(int i=0; i<n ;i++){
		x[i]=X[i];
		bl[i/bs].push_back(x[i]);
	}
	for(int i=0; i<bc ;i++) yena(i);
}
int update(int i, int y){
	if(++rnd==bs){
		rnd=0;
		iu();
	}
	int pos=find(x[i]);
	for(auto& cur:bl[pos]) if(cur==x[i]) cur=2e9;
	for(int i=1; i<bl[pos].size() ;i++) if(bl[pos][i]<bl[pos][i-1]) swap(bl[pos][i-1],bl[pos][i]);
	bl[pos].pop_back();yena(pos);
	x[i]=y;
	pos=find(x[i]);
	bl[pos].push_back(x[i]);
	for(int i=bl[pos].size()-1; i>=1 ;i--) if(bl[pos][i]<bl[pos][i-1]) swap(bl[pos][i-1],bl[pos][i]);
	yena(pos);
	return sakura();
}

Compilation message

elephants.cpp: In function 'void yena(int)':
elephants.cpp:22:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr==bl[pos].size()) dp[pos][i]=1,en[pos][i]=bl[pos][i]+l+1;
      ~~~^~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<bl[pos].size() ;i++) if(bl[pos][i]<bl[pos][i-1]) swap(bl[pos][i-1],bl[pos][i]);
               ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 334 ms 1340 KB Output is correct
8 Correct 352 ms 2424 KB Output is correct
9 Correct 418 ms 3908 KB Output is correct
10 Correct 417 ms 3704 KB Output is correct
11 Correct 398 ms 3448 KB Output is correct
12 Correct 648 ms 3848 KB Output is correct
13 Correct 428 ms 3448 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 334 ms 1340 KB Output is correct
8 Correct 352 ms 2424 KB Output is correct
9 Correct 418 ms 3908 KB Output is correct
10 Correct 417 ms 3704 KB Output is correct
11 Correct 398 ms 3448 KB Output is correct
12 Correct 648 ms 3848 KB Output is correct
13 Correct 428 ms 3448 KB Output is correct
14 Incorrect 127 ms 3200 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 334 ms 1340 KB Output is correct
8 Correct 352 ms 2424 KB Output is correct
9 Correct 418 ms 3908 KB Output is correct
10 Correct 417 ms 3704 KB Output is correct
11 Correct 398 ms 3448 KB Output is correct
12 Correct 648 ms 3848 KB Output is correct
13 Correct 428 ms 3448 KB Output is correct
14 Incorrect 127 ms 3200 KB Output isn't correct
15 Halted 0 ms 0 KB -