oj.uz

Submission #1113788

# Submission time Handle Problem Language Result Execution time Memory
1113788 2024-11-17T13:02:05 Z Zero_OP Building Bridges (CEOI17_building) C++14
100 / 100
 171 ms 91800 KB 
//Just some random thing in my mind
#include <bits/stdc++.h>

using namespace std;

const long long inf = 4e18;

struct line{
    long long a, b, p;
    line(long long a = 0, long long b = 0, long long p = 0) : a(a), b(b), p(p) {}
    long long eval(long long x){ return a * x + b; }
    bool operator < (const long long& o) const { return p < o; }

    friend bool operator < (const line& d1, const line& d2){
        return make_pair(d1.a, d1.b) > make_pair(d2.a, d2.b);
    }
};

long long divi(long long a, long long b){
    return a / b - ((a % b) != 0 && (a ^ b) < 0);
}

void isect(line& d1, const line& d2){
    if(d1.a == d2.a) d1.p = (d1.b < d2.b ? inf : -inf);
    else d1.p = divi(d2.b - d1.b, d1.a - d2.a);
}

struct convex_hull_trick{
    deque<line> v;
    convex_hull_trick() : v() {}

    void add(long long a, long long b){
        line d(a, b, inf);
        if(!v.empty()) isect(v.back(), d);
        while((int)v.size() > 1 && v[(int)v.size() - 2].p >= v.back().p){
            v.pop_back();
            isect(v.back(), d);
        }

        v.push_back(d);
    }

//    long long query(long long x){
//        int id = lower_bound(v.begin(), v.end(), x) - v.begin();
//        return v[id].eval(x);
//    }

    long long query(long long x){
        while((int)v.size() > 1 && v[0].eval(x) >= v[1].eval(x)) v.pop_front();
        return v[0].eval(x);
    }
};

template<typename T>
void merge_sort(vector<T>& a, const vector<T>& b){
    vector<T> c;
    int i = 0, j = 0;
    while(i < (int)a.size() || j < (int)b.size()){
        if(i == (int)a.size()) c.emplace_back(b[j++]);
        else if(j == (int)b.size()) c.emplace_back(a[i++]);
        else if(a[i] < b[j]) c.emplace_back(a[i++]);
        else c.emplace_back(b[j++]);
    }
    swap(a, c);
}

const int MAX = 1e5 + 5;

int N, timerNodes, ln[MAX * 2], rn[MAX * 2];
long long dp[MAX], h[MAX], w[MAX];
vector<line> lines[MAX * 2];
vector<pair<int, int>> queries[MAX * 2];

int build(int l, int r){
    if(l == r) {
        ++timerNodes;
        queries[timerNodes].emplace_back(-2 * h[l], l);
        return timerNodes;
    }
    int mid = l + r >> 1, cur = ++timerNodes;
    ln[cur]=  build(l, mid);
    rn[cur] = build(mid + 1, r);
    queries[cur]=  queries[ln[cur]];
    merge_sort(queries[cur], queries[rn[cur]]);
    return cur;
}

void solve(int l, int r, int cur){
    if(l == r) {
        lines[cur].emplace_back(h[l], h[l] * h[l] + dp[l] - w[l]);
        return;
    }

    int mid = l + r >> 1;
    solve(l, mid, ln[cur]);
    convex_hull_trick cht;
    for(auto d : lines[ln[cur]]) cht.add(d.a, d.b);
    for(auto [slope, i] : queries[rn[cur]]){
        dp[i] = min(dp[i], cht.query(slope) + w[i - 1] + h[i] * h[i]);
    }

    solve(mid + 1, r, rn[cur]);

    lines[cur] = lines[ln[cur]];
    merge_sort(lines[cur], lines[rn[cur]]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> N;
    for(int i = 1; i <= N; ++i) cin >> h[i];
    for(int i = 1; i <= N; ++i) cin >> w[i], w[i] += w[i - 1];

    for(int i = 2; i <= N; ++i) dp[i] = inf;
    int root = build(1, N);
    solve(1, N, root);

    cout << dp[N] << '\n';

    return 0;
}

Compilation message

building.cpp: In function 'int build(int, int)':
building.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |     int mid = l + r >> 1, cur = ++timerNodes;
      |               ~~^~~
building.cpp: In function 'void solve(int, int, int)':
building.cpp:94:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |     for(auto [slope, i] : queries[rn[cur]]){
      |              ^

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 89396 KB Output is correct
2 Correct 159 ms 89520 KB Output is correct
3 Correct 171 ms 89524 KB Output is correct
4 Correct 155 ms 89520 KB Output is correct
5 Correct 134 ms 89520 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12880 KB Output is correct
2 Correct 3 ms 12880 KB Output is correct
3 Correct 3 ms 12880 KB Output is correct
4 Correct 4 ms 13392 KB Output is correct
5 Correct 4 ms 13392 KB Output is correct
6 Correct 160 ms 89396 KB Output is correct
7 Correct 159 ms 89520 KB Output is correct
8 Correct 171 ms 89524 KB Output is correct
9 Correct 155 ms 89520 KB Output is correct
10 Correct 134 ms 89520 KB Output is correct
11 Correct 166 ms 89516 KB Output is correct
12 Correct 168 ms 89520 KB Output is correct
13 Correct 152 ms 89400 KB Output is correct
14 Correct 165 ms 89520 KB Output is correct
15 Correct 140 ms 91800 KB Output is correct
16 Correct 146 ms 89520 KB Output is correct
17 Correct 123 ms 89520 KB Output is correct
18 Correct 119 ms 89520 KB Output is correct