oj.uz

Submission #519405

# Submission time Handle Problem Language Result Execution time Memory
519405 2022-01-26T10:19:17 Z hoanghq2004 Building Bridges (CEOI17_building) C++14
0 / 100
 62 ms 65128 KB 
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e6 + 10;

int n;
int h[N];
long long s[N];

struct Line {
    long long a, b;
    Line() {
        a = 0, b = 1e18;
    }
    Line(long long a, long long b): a(a), b(b) {}
    long long operator()(long long x) {
        return a * x + b;
    }
} st[N * 4];

void add(int id, int L, int R, Line l) {
    int m = L + R >> 1;
    bool lft = st[id](L) > l(L);
    bool mid = st[id](m) > l(m);
    if (mid) swap(l, st[id]);
    if (L == R - 1) return;
    if (lft != mid) add(id * 2, L, m, l);
    else add(id * 2 + 1, m, R, l);
}

long long get(int id, int L, int R, int i) {
    if (L == R - 1) return st[id](i);
    int mid = L + R >> 1;
    if (i < mid) return min(get(id * 2, L, mid, i), st[id](i));
    else return min(get(id * 2 + 1, mid, R, i), st[id](i));
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) cin >> s[i];
    for (int i = 1; i <= n; ++i) s[i] += s[i - 1];
    int M = 1e6 + 1;
    add(1, 0, M, Line(- 2 * h[1], s[1] + 1LL * h[1] * h[1]));
    long long now = 0;
    for (int i = 2; i <= n; ++i) {
        now = get(1, 0, M, h[i]) + 1LL * h[i] * h[i] + s[i - 1];
        add(1, 0, M, Line(- 2 * h[i], now - s[i] + 1LL * h[i] * h[i]));
    }
    cout << now;
}

Compilation message

building.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
building.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
building.cpp: In function 'void add(int, int, int, Line)':
building.cpp:31:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int m = L + R >> 1;
      |             ~~^~~
building.cpp: In function 'long long int get(int, int, int, int)':
building.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid = L + R >> 1;
      |               ~~^~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 62900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 65128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 62900 KB Output isn't correct
2 Halted 0 ms 0 KB -