Submission #988642

#	Time	Username	Problem	Language	Result	Execution time	Memory
988642		parlimoos	Building Bridges (CEOI17_building)	C++17	100 / 100	461 ms	13392 KiB

building

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<ll , x>
#define endl '\n'

int n;
vector<ll> w , h;
ll dp[200000] , inf[200000][2];
set<arr(2)> pt;

void init(){
    for(int i = 1 ; i < n ; i++) w[i] += w[i - 1];
    for(int i = 0 ; i < n ; i++){
        inf[i][1] = (h[i] * h[i]) , inf[i][0] = (h[i] * h[i]) - w[i];
        if(i > 0) inf[i][1] += w[i - 1];
    }
}
bool jg(ll c , int i , int j){
    return (dp[i] - (2 * c * h[i]) <= dp[j] - (2 * c * h[j]));
}
int bsMx(int i){
    int l = 0 , r = int(1e6) + 1;
    while(r - l - 1 > 1){
        int c = (r + l + 1) >> 1;
        int inx = (*(--pt.ub({c , int(1e9)})))[1];
        if(h[inx] < h[i]) l = c - 1;
        else if(jg(c , i , inx)) l = c - 1;
        else r = c;
    }
    if(r - l - 1 == 1){
        int inx = (*(--pt.ub({l + 1 , int(1e9)})))[1];
        if(h[inx] < h[i]) return l + 1;
        else if(jg(l + 1 , i , inx)) return l + 1;
    }
    return l;
}
int bsMn(int i , int r){
    int l = -1;
    while(r - l - 1 > 1){
        int c = (r + l + 1) >> 1;
        int inx = (*(--pt.ub({c , int(1e9)})))[1];
        if(jg(c , i , inx)) r = c;
        else l = c - 1;
    }
    if(r - l - 1 == 1){
        int inx = (*(--pt.ub({r - 1 , int(1e9)})))[1];
        if(jg(r - 1 , i , inx)) return r - 1;
    }
    return r;
}
void addEl(int i){
    if(pt.empty()){
        pt.insert({0 , i});
        return;
    }
    int r = bsMx(i);
    int l = bsMn(i , r + 1);
    if(l > r) return;
    auto itr1 = pt.lb({l , -1}) , itr2 = pt.ub({r , int(1e9)});
    if(itr1 == itr2){
        pt.insert({l , i});
        return;
    }
    vector<arr(2)> dls , adds;
    itr2--;
    while(true){
        dls.pb((*itr1));
        if(itr2 == itr1){
            adds.pb({r + 1 , (*itr2)[1]});
            if((*++itr1)[0] == r + 1) adds.cl();
            break;
        }
        itr1++;
    }
    pt.insert({l , i});
    for(auto &el : dls) pt.erase(el);
    for(auto &el : adds) pt.insert(el);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0 ; i < n ; i++){
        h.pb(0);
        cin >> h.back();
    }
    for(int i = 0 ; i < n ; i++){
        w.pb(0);
        cin >> w.back();
    }
    init();
    dp[n - 1] += inf[n - 1][1];
    addEl(n - 1);
    for(int i = n - 2 ; i >= 0 ; i--){
        // for(auto el : pt) cout << el[0] << " " << el[1] << ",,\n";
        // cout << "-----\n";
        int inx = (*(--pt.ub({h[i] , int(1e9)})))[1];
        dp[i] = dp[inx] + inf[i][0] - (2 * h[i] * h[inx]);
        if(i > 0) dp[i] += inf[i][1];
        // cout << dp[i] << "!!\n";
        addEl(i);
    }
    // cout << jg(5 , 2 , 3) << "::\n";
    cout << dp[0] << "\n";
}

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