oj.uz

Submission #988625

# Submission time Handle Problem Language Result Execution time Memory
988625 2024-05-25T10:30:38 Z parlimoos Building Bridges (CEOI17_building) C++14
60 / 100
 297 ms 6224 KB 
//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];
}

Compilation message

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2552 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 4496 KB Output is correct
2 Correct 291 ms 5472 KB Output is correct
3 Correct 296 ms 5528 KB Output is correct
4 Correct 250 ms 5336 KB Output is correct
5 Correct 266 ms 6224 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2552 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 297 ms 4496 KB Output is correct
7 Correct 291 ms 5472 KB Output is correct
8 Correct 296 ms 5528 KB Output is correct
9 Correct 250 ms 5336 KB Output is correct
10 Correct 266 ms 6224 KB Output is correct
11 Correct 245 ms 5604 KB Output is correct
12 Correct 296 ms 5612 KB Output is correct
13 Incorrect 116 ms 5716 KB Output isn't correct
14 Halted 0 ms 0 KB -