제출 #988625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
988625		parlimoos	Building Bridges (CEOI17_building)	C++14	60 / 100	297 ms	6224 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];
    }
}
bool jg(int c , int i , int j){
    return (dp[i] - ((2ll * c) * h[i]) <= dp[j] - ((2ll * 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 + r , 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){
        dd[0] = r - 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);
    // cout << i << " " << l << " " << r << "*\n";
    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] - ((2ll * h[i]) * (1ll * h[inx]));
        if(i > 0) dp[i] += inf[i][1];
        // cout << dp[i] << "!!\n";
        addEl(i);
    }
    // cout << jg(0 , 1 , 2) << "::\n";
    cout << dp[0];
}

컴파일 시 표준 에러 (stderr) 메시지

building.cpp: In function 'int main()':
building.cpp:115:47: warning: narrowing conversion of 'h.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i))' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  115 |         int inx = (*(--pt.ub({h[i] , int(1e9)})))[1];
      |                                               ^

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