oj.uz

Submission #988627

# Submission time Handle Problem Language Result Execution time Memory
988627 2024-05-25T10:37:10 Z parlimoos Building Bridges (CEOI17_building) C++14
60 / 100
 316 ms 7840 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);

    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];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 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 2 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 6480 KB Output is correct
2 Correct 316 ms 6232 KB Output is correct
3 Correct 315 ms 6432 KB Output is correct
4 Correct 271 ms 6480 KB Output is correct
5 Correct 291 ms 7840 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 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 2 ms 2396 KB Output is correct
6 Correct 309 ms 6480 KB Output is correct
7 Correct 316 ms 6232 KB Output is correct
8 Correct 315 ms 6432 KB Output is correct
9 Correct 271 ms 6480 KB Output is correct
10 Correct 291 ms 7840 KB Output is correct
11 Correct 260 ms 6444 KB Output is correct
12 Correct 309 ms 6432 KB Output is correct
13 Incorrect 117 ms 6232 KB Output isn't correct
14 Halted 0 ms 0 KB -