oj.uz

Submission #988628

# Submission time Handle Problem Language Result Execution time Memory
988628 2024-05-25T10:49:31 Z parlimoos Building Bridges (CEOI17_building) C++17
60 / 100
 312 ms 7844 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<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 + 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){
        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);

    // freopen("in.txt" , "r" , stdin);

    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(0 , 1 , 2) << "::\n";
    cout << dp[0] << "\n";
}

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 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2392 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 6432 KB Output is correct
2 Correct 307 ms 6424 KB Output is correct
3 Correct 296 ms 6424 KB Output is correct
4 Correct 309 ms 6436 KB Output is correct
5 Correct 262 ms 7844 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 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2392 KB Output is correct
6 Correct 299 ms 6432 KB Output is correct
7 Correct 307 ms 6424 KB Output is correct
8 Correct 296 ms 6424 KB Output is correct
9 Correct 309 ms 6436 KB Output is correct
10 Correct 262 ms 7844 KB Output is correct
11 Correct 264 ms 6472 KB Output is correct
12 Correct 312 ms 6432 KB Output is correct
13 Incorrect 114 ms 6424 KB Output isn't correct
14 Halted 0 ms 0 KB -