Submission #48363

#	Time	Username	Problem	Language	Result	Execution time	Memory
48363		wzy	Building Bridges (CEOI17_building)	C++11	0 / 100	138 ms	4004 KiB

building

#include <bits/stdc++.h>
using namespace std;

long long w[100005] , h[100005];
long long n;
long long dp[100005];
struct line{
    long long x , y;
    line(long long x , long long y){
        this->x = x , this->y = y;
    }
};
template <class type> 
class CHT{
    public : 
    bool cmp(type a , type b , type c){
        double f1 = ((c.y) - (a.y)) * ((a.x) - (b.x)) , f2 = ((b.y) - (a.y)) * ((a.x) - (c.x));
        return ((double)((double) (c.y) - (a.y)) / ((double) (b.y) - (a.y)) ) <= ((double) ((double) (a.x) - (c.x)) / ((double) (a.x) - (b.x)) ); 
        return f1 <= f2;
    }
    int returnsize(){
    	return cht.size();
    }
    void addLINE(type a){
            while(cht.size() >= 2 && cmp(cht[cht.size() - 2] , cht[cht.size() - 1] , a)){
                cht.pop_back();
            }
        cht.push_back(a);
    }
    long long eval(type b , int a){
        int w = (b.x) * a + (b.y);
        return w;
    }
    long long querymin(int x){
        if(cht.size() == 0) return ((long long) 1e18);
        int l = 0 , r = cht.size() - 1;
        r--;
        int ansj = -1;
        while(l<=r){
            int mid = (l+r)/2;
            if(eval(cht[mid] , x) >= eval(cht[mid + 1] , x)){
                l = mid + 1;
                ansj = mid;
            }
            else r = mid - 1;
        }
        long long bestvalue = eval(cht.front() , x);
        if(ansj != -1) bestvalue = min(bestvalue , eval(cht[ansj] , x));
        ansj ++;
        if(ansj < cht.size()) bestvalue = min(bestvalue , eval(cht[ansj] , x));

        return bestvalue;
    }
    void merge(vector<type> nhcht){
    	vector<type> newcht;
    	int A = 0 , B = 0;
    	for(int i = 0 ; i < (nhcht.size() + cht.size()) ; i++){
    		if(A == nhcht.size()){
	    		while(newcht.size() >= 2 && cmp(newcht[newcht.size() - 2] , newcht[newcht.size() - 1] , cht[B])){
	                newcht.pop_back();
	            }
	            newcht.push_back(cht[B]);
	            ++B;
    		}
    		else if(B == cht.size()){
	    		while(newcht.size() >= 2 && cmp(newcht[newcht.size() - 2] , newcht[newcht.size() - 1] , nhcht[A])){
	                newcht.pop_back();
	            }
	            newcht.push_back(nhcht[A]);
	            ++A;
    		}
    		else{
    			if(cht[B].x > nhcht[A].x){
    				while(newcht.size() >= 2 && cmp(newcht[newcht.size() - 2] , newcht[newcht.size() - 1] , cht[B])){
               			newcht.pop_back();
            		}
            		newcht.push_back(cht[B]);
           		 ++B;
    			}
    			else{
		    		while(newcht.size() >= 2 && cmp(newcht[newcht.size() - 2] , newcht[newcht.size() - 1] , nhcht[A])){
		                newcht.pop_back();
		            }
		            newcht.push_back(nhcht[A]);
		            ++A;    				
    			}
    		}
    	}
    	cht = newcht;
    }
    vector<type> mergefunc(){
    	return cht;
    }
    void clearv(){
    	cht.clear();
    }
    long long querymax(int x){
        if(cht.size() == 0) return 0;
        int l = 0 , r = cht.size() - 1;
        r--;
        int ansj = -1;
        while(l<=r){
            int mid = (l+r)/2;
            if(eval(cht[mid] , x) <= eval(cht[mid+1],x)){
                l = mid + 1;
                ansj = mid;
            }
            else r = mid - 1;
        }
        long long bestvalue = eval(cht.front() , x);
        if(ansj != -1) bestvalue = max(bestvalue , eval(cht[ansj] , x));
        ansj++;
        if(ansj < cht.size()) bestvalue = max(bestvalue ,eval(cht[ansj] , x));
        return bestvalue;
    }
 //   private :
    vector<type> cht;
}; 

CHT<line> chts[32];

void addline(line a){
	chts[0].addLINE(a);
	for(int i = 0 ; i < 32 ; i++){
		if((chts[i].returnsize()) > (1LL<<i)){
			chts[i+1].merge(chts[i].mergefunc());
			chts[i].clearv();
		}
	}
}


long long query(int x){
	long long bestvalue = (long long) 1e18;
	for(int i = 0 ; i < 32 ; i++){
		bestvalue = min(bestvalue , chts[i].querymin(x));
	}
	return bestvalue;
}


int main(){
	scanf("%lld" , &n);
	dp[0] = 0;
	for(int i = 1 ; i <=n ;i ++){
		scanf("%lld" , &h[i]);
	}
	w[0] = 0;
	for(int i = 1 ; i <=n ;i ++){
		scanf("%lld" , &w[i]);
		w[i] += w[i-1];
	}
	dp[1] = 0;
	addline(line(-2*h[1] , h[1]*h[1]  - w[1] + dp[1]));
	for(int i = 2 ; i <= n ;i ++){
		dp[i] = query(h[i]) + h[i]*h[i] + w[i-1];
		addline(line(-2*h[i] , h[i]*h[i] - w[i] + dp[i]));
	}
	printf("%lld\n" , dp[n]);
}

Compilation message (stderr)

building.cpp: In instantiation of 'void CHT<type>::merge(std::vector<_Tp>) [with type = line]':
building.cpp:126:39:   required from here
building.cpp:57:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0 ; i < (nhcht.size() + cht.size()) ; i++){
                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:58:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(A == nhcht.size()){
building.cpp:65:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       else if(B == cht.size()){
building.cpp: In instantiation of 'long long int CHT<type>::querymin(int) [with type = line]':
building.cpp:136:49:   required from here
building.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ansj < cht.size()) bestvalue = min(bestvalue , eval(cht[ansj] , x));
building.cpp: In function 'int main()':
building.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &n);
  ~~~~~^~~~~~~~~~~~~
building.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld" , &h[i]);
   ~~~~~^~~~~~~~~~~~~~~~
building.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld" , &w[i]);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40