oj.uz

Submission #284912

# Submission time Handle Problem Language Result Execution time Memory
284912 2020-08-28T07:57:23 Z TMJN Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 8552 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int bsize=500;

int N,A[150000],B[150000],C[150000],P[150000],L,D[1000],c;
vector<int>vb[1000];
pair<int,int>pp[150000];

void update_bucket(int t){
	for(int i:vb[t]){
		C[i]=t;
	}
	for(int i=vb[t].size()-1;i>=0;i--){
		int l,r;
		l=i;
		r=vb[t].size();
		while(l+1!=r){
			int m=(l+r)/2;
			if(P[vb[t][i]]+L<P[vb[t][m]]){
				r=m;
			}
			else{
				l=m;
			}
		}
		if(r==vb[t].size()){
			A[vb[t][i]]=1;
			B[vb[t][i]]=P[vb[t][i]]+L;
		}
		else{
			A[vb[t][i]]=A[vb[t][r]]+1;
			B[vb[t][i]]=B[vb[t][r]];
		}
	}
}

void erase(int t){
	int id=C[t];
	for(int i=0;i<vb[id].size();i++){
		if(vb[id][i]==t){
			vb[id].erase(vb[id].begin()+i);
		}
	}
	update_bucket(id);
}

void add(int t,int x){
	P[t]=x;
	D[0]=0;
	for(int i=0;i<(N-1)/bsize+1;i++){
		if(vb[i].empty()){
			D[i+1]=D[i];
		}
		else{
			D[i]=P[vb[i].front()];
			D[i+1]=P[vb[i].back()];
		}
	}
	D[(N-1)/bsize+1]=2000000000;
	int id;
	for(int i=0;i<(N-1)/bsize+1;i++){
		if(x<=D[i+1]){
			id=i;
			break;
		}
	}
	vb[id].push_back(t);
	for(int i=vb[id].size()-2;i>=0;i--){
		if(P[vb[id][i]]>P[vb[id][i+1]]){
			swap(vb[id][i],vb[id][i+1]);
		}
	}
	update_bucket(id);
}

int calc(){
	int c=0;
	int p=-1;
	for(int i=0;i<(N-1)/bsize+1;i++){
		if(vb[i].empty()||P[vb[i].back()]<=p)continue;
		int l,r;
		l=-1;
		r=vb[i].size()-1;
		while(l+1!=r){
			int m=(l+r)/2;
			if(p<P[vb[i][m]]){
				r=m;
			}
			else{
				l=m;
			}
		}
		c+=A[vb[i][r]];
		p=B[vb[i][r]];
	}
	return c;
}


void big_update(){
	for(int i=0;i<N;i++){
		pp[i]={P[i],i};
	}
	sort(pp,pp+N);
	for(int i=0;i<(N-1)/bsize+1;i++){
		vector<int>v;
		swap(v,vb[i]);
		for(int j=i*bsize;j<(i+1)*bsize&&j<N;j++){
			vb[i].push_back(pp[j].second);
		}
		update_bucket(i);
	}
}

void init(int n, int l, int X[]){
	N=n;
	L=l;
	for(int i=0;i<N;i++){
		P[i]=X[i];
	}
	big_update();
	
}

int update(int i, int y){
	erase(i);
	add(i,y);
	c++;
	if(c%1000==0){
		big_update();
	}
	return calc();
}

Compilation message

elephants.cpp: In function 'void update_bucket(int)':
elephants.cpp:27:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   if(r==vb[t].size()){
      |      ~^~~~~~~~~~~~~~
elephants.cpp: In function 'void erase(int)':
elephants.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0;i<vb[id].size();i++){
      |              ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1498 ms 2328 KB Output is correct
8 Correct 1559 ms 2592 KB Output is correct
9 Correct 1377 ms 4156 KB Output is correct
10 Correct 2457 ms 3944 KB Output is correct
11 Correct 1857 ms 3704 KB Output is correct
12 Correct 2029 ms 3832 KB Output is correct
13 Correct 2787 ms 3704 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1498 ms 2328 KB Output is correct
8 Correct 1559 ms 2592 KB Output is correct
9 Correct 1377 ms 4156 KB Output is correct
10 Correct 2457 ms 3944 KB Output is correct
11 Correct 1857 ms 3704 KB Output is correct
12 Correct 2029 ms 3832 KB Output is correct
13 Correct 2787 ms 3704 KB Output is correct
14 Correct 2434 ms 2940 KB Output is correct
15 Correct 2355 ms 3328 KB Output is correct
16 Correct 3262 ms 4288 KB Output is correct
17 Correct 3182 ms 5060 KB Output is correct
18 Correct 3441 ms 5208 KB Output is correct
19 Correct 3002 ms 4916 KB Output is correct
20 Correct 3182 ms 5192 KB Output is correct
21 Correct 3228 ms 5112 KB Output is correct
22 Correct 4276 ms 4984 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1498 ms 2328 KB Output is correct
8 Correct 1559 ms 2592 KB Output is correct
9 Correct 1377 ms 4156 KB Output is correct
10 Correct 2457 ms 3944 KB Output is correct
11 Correct 1857 ms 3704 KB Output is correct
12 Correct 2029 ms 3832 KB Output is correct
13 Correct 2787 ms 3704 KB Output is correct
14 Correct 2434 ms 2940 KB Output is correct
15 Correct 2355 ms 3328 KB Output is correct
16 Correct 3262 ms 4288 KB Output is correct
17 Correct 3182 ms 5060 KB Output is correct
18 Correct 3441 ms 5208 KB Output is correct
19 Correct 3002 ms 4916 KB Output is correct
20 Correct 3182 ms 5192 KB Output is correct
21 Correct 3228 ms 5112 KB Output is correct
22 Correct 4276 ms 4984 KB Output is correct
23 Correct 6881 ms 8304 KB Output is correct
24 Correct 7474 ms 8300 KB Output is correct
25 Correct 6221 ms 8552 KB Output is correct
26 Execution timed out 9049 ms 8440 KB Time limit exceeded
27 Halted 0 ms 0 KB -