oj.uz

Submission #519408

# Submission time Handle Problem Language Result Execution time Memory
519408 2022-01-26T10:22:27 Z hoanghq2004 Building Bridges (CEOI17_building) C++14
100 / 100
 94 ms 65304 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62952 KB Output is correct
2 Correct 28 ms 62924 KB Output is correct
3 Correct 27 ms 62856 KB Output is correct
4 Correct 27 ms 62936 KB Output is correct
5 Correct 27 ms 62964 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 64104 KB Output is correct
2 Correct 88 ms 65092 KB Output is correct
3 Correct 77 ms 65132 KB Output is correct
4 Correct 66 ms 64964 KB Output is correct
5 Correct 71 ms 64980 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62952 KB Output is correct
2 Correct 28 ms 62924 KB Output is correct
3 Correct 27 ms 62856 KB Output is correct
4 Correct 27 ms 62936 KB Output is correct
5 Correct 27 ms 62964 KB Output is correct
6 Correct 63 ms 64104 KB Output is correct
7 Correct 88 ms 65092 KB Output is correct
8 Correct 77 ms 65132 KB Output is correct
9 Correct 66 ms 64964 KB Output is correct
10 Correct 71 ms 64980 KB Output is correct
11 Correct 94 ms 65216 KB Output is correct
12 Correct 75 ms 65088 KB Output is correct
13 Correct 62 ms 65196 KB Output is correct
14 Correct 71 ms 65304 KB Output is correct
15 Correct 57 ms 64952 KB Output is correct
16 Correct 75 ms 64984 KB Output is correct
17 Correct 56 ms 65120 KB Output is correct
18 Correct 53 ms 65092 KB Output is correct