제출 #988619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
988619		parlimoos	Building Bridges (CEOI17_building)	C++14	0 / 100	297 ms	5412 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<int , x>
#define endl '\n'

int n;
vector<ll> w , h;
ll dp[100000] , inf[100000][2];
set<arr(2)> pt;
arr(2) dd = {-1 , -1};

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];
    }
}
int bsMx(int i){
    int l = 0 , r = int(1e6) + 1;
    while(r - l - 1 > 1){
        int c = (r + l + 1) >> 1;
        dd[0] = c;
        int inx = (*(--pt.ub(dd)))[1];
        if(h[inx] < h[i]) l = c - 1;
        else{
            if(dp[inx] - ((2ll * c) * h[inx]) < dp[i] - ((2ll * c) * h[i])) r = c;
            else l = c - 1;
        }
    }
    if(r - l - 1 == 1){
        dd[0] = l + 1;
        int inx = (*(--pt.ub(dd)))[1];
        if(h[inx] < h[i]) return l + 1;
        else if(dp[inx] - ((2ll * (l + 1)) * h[inx]) >= dp[i] - ((2ll * (l + 1)) * h[i])) 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;
        dd[0] = c;
        int inx = (*(--pt.ub(dd)))[1];
        if(dp[i] - ((2ll * c) * h[i]) < dp[inx] - ((2ll * c) * h[inx])) r = c;
        else l = c - 1;
    }
    if(r - l - 1 == 1){
        dd[0] = r - 1;
        int inx = (*(--pt.ub(dd)))[1];
        if(dp[i] - ((2ll * (r - 1)) * h[i]) < dp[inx] - ((2ll * (r - 1)) * h[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;
    dd[0] = l;
    auto itr1 = pt.lb(dd);
    dd[0] = r;
    auto itr2 = pt.ub(dd);
    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--){
        dd[0] = h[i];
        int inx = (*(--pt.ub(dd)))[1];
        dp[i] = dp[inx] + inf[i][0] - ((2ll * h[i]) * (1ll * h[inx]));
        if(i > 0) dp[i] += inf[i][1];
        addEl(i);
    }
    cout << dp[0];
}

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