oj.uz

Submission #284871

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

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()-1;i++){
		if(vb[id][i]==t){
			swap(vb[id][i],vb[id][i+1]);
		}
	}
	vb[id].pop_back();
	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()-1;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 874 ms 1464 KB Output is correct
8 Correct 935 ms 2140 KB Output is correct
9 Correct 1067 ms 3248 KB Output is correct
10 Correct 1946 ms 3192 KB Output is correct
11 Correct 1591 ms 4052 KB Output is correct
12 Correct 1539 ms 4308 KB Output is correct
13 Correct 2257 ms 3888 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 874 ms 1464 KB Output is correct
8 Correct 935 ms 2140 KB Output is correct
9 Correct 1067 ms 3248 KB Output is correct
10 Correct 1946 ms 3192 KB Output is correct
11 Correct 1591 ms 4052 KB Output is correct
12 Correct 1539 ms 4308 KB Output is correct
13 Correct 2257 ms 3888 KB Output is correct
14 Correct 1694 ms 3328 KB Output is correct
15 Correct 1486 ms 3448 KB Output is correct
16 Correct 2256 ms 4704 KB Output is correct
17 Correct 2426 ms 5624 KB Output is correct
18 Correct 2687 ms 5636 KB Output is correct
19 Correct 2510 ms 5832 KB Output is correct
20 Correct 2505 ms 5764 KB Output is correct
21 Correct 2560 ms 5624 KB Output is correct
22 Correct 3125 ms 5268 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 874 ms 1464 KB Output is correct
8 Correct 935 ms 2140 KB Output is correct
9 Correct 1067 ms 3248 KB Output is correct
10 Correct 1946 ms 3192 KB Output is correct
11 Correct 1591 ms 4052 KB Output is correct
12 Correct 1539 ms 4308 KB Output is correct
13 Correct 2257 ms 3888 KB Output is correct
14 Correct 1694 ms 3328 KB Output is correct
15 Correct 1486 ms 3448 KB Output is correct
16 Correct 2256 ms 4704 KB Output is correct
17 Correct 2426 ms 5624 KB Output is correct
18 Correct 2687 ms 5636 KB Output is correct
19 Correct 2510 ms 5832 KB Output is correct
20 Correct 2505 ms 5764 KB Output is correct
21 Correct 2560 ms 5624 KB Output is correct
22 Correct 3125 ms 5268 KB Output is correct
23 Correct 6668 ms 12408 KB Output is correct
24 Correct 7172 ms 12476 KB Output is correct
25 Correct 6184 ms 12340 KB Output is correct
26 Execution timed out 9023 ms 12280 KB Time limit exceeded
27 Halted 0 ms 0 KB -