Submission #284879

#	Time	Username	Problem	Language	Result	Execution time	Memory
284879		TMJN	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	9088 ms	7292 KiB

elephants

    #include "elephants.h"
    #include <bits/stdc++.h>
    using namespace std;
    const int bsize=400;
     
    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);
              	break;
    		}
    	}
    	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 (stderr)

elephants.cpp: In function 'void update_bucket(int)':
elephants.cpp:27:11: 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:19: 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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 0 / 3