oj.uz

Submission #37026

# Submission time Handle Problem Language Result Execution time Memory
37026 2017-12-20T14:13:18 Z DoanPhuDuc Building Bridges (CEOI17_building) C++
100 / 100
 113 ms 17836 KB 
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 1e5 + 10;
const int A = 1e6;
const LL INFL = LLONG_MAX;

struct Line {
    LL a, b;
    Line () {
        a = 0;
        b = INFL;
    }
    Line (LL a, LL b) : a(a), b(b) {}
    LL F(LL x) {
        return a * x + b;
    }
};

int n;
int a[N], b[N];

LL S[N], f[N];

struct SegmenTree {
    #define m ((l + r) >> 1)
    struct Node {
        Line d;
        int l, r;
        Node *left, *right;
        Node () {}
        Node (int l, int r) : l(l), r(r), left(NULL), right(NULL) {}
    };
    Node *Root;
    void Init(int n) {
        Root = new Node(0, n);
    }
    void PushDown(Node *k) {
        int l = k -> l, r = k -> r;
        if (l < r && k -> left == NULL) {
            k -> left = new Node(l, m);
            k -> right = new Node(m + 1, r);
        }
    }
    void Update(Node *k, int i, int j, Line d) {
        PushDown(k);
        int l = k -> l, r = k -> r;
        if (l > j || r < i) return;
        if (i <= l && r <= j) {
            Line A = k -> d, B = d;
            if (A.F(l) > B.F(l)) swap(A, B);
            if (l == r) k -> d = A;
                else {
                    if (A.F(m) <= B.F(m)) {
                        k -> d= A;
                        Update(k -> right, i, j, B);
                    } else {
                        k -> d = B;
                        Update(k -> left, i, j, A);
                    }
                }
        }
    }
    LL Query(Node *k, LL x) {
        if (k == NULL) return INFL;
        int l = k -> l, r = k -> r;
        if (l > x || r < x) return INFL;
        if (l == r) return k -> d.F(x);
        LL ans = k -> d.F(x);
           ans = min(ans, Query(k -> left, x));
           ans = min(ans, Query(k -> right, x));
        return ans;
    }
    #undef m
} ST;

LL sqr(LL x) {
    return x * x;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d", &n);
    FOR(i, 1, n) scanf("%d", &a[i]);
    FOR(i, 1, n) scanf("%d", &b[i]);
    FOR(i, 1, n) S[i] = S[i - 1] + b[i];
    f[1] = 0;
    ST.Init(A);
    FOR(i, 2, n) {
        ST.Update(ST.Root, 0, A, Line(-2LL * a[i - 1], f[i - 1] + sqr(a[i - 1]) - S[i - 1]));
        f[i] = ST.Query(ST.Root, a[i]) + sqr(a[i]) + S[i - 1];
    }
    printf("%lld", f[n]);
    return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:97:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
building.cpp:98:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &a[i]);
                                    ^
building.cpp:99:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &b[i]);
                                    ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4372 KB Output is correct
2 Correct 0 ms 4372 KB Output is correct
3 Correct 0 ms 4372 KB Output is correct
4 Correct 0 ms 4504 KB Output is correct
5 Correct 0 ms 4504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5164 KB Output is correct
2 Correct 86 ms 5164 KB Output is correct
3 Correct 76 ms 5164 KB Output is correct
4 Correct 83 ms 4636 KB Output is correct
5 Correct 53 ms 10444 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4372 KB Output is correct
2 Correct 0 ms 4372 KB Output is correct
3 Correct 0 ms 4372 KB Output is correct
4 Correct 0 ms 4504 KB Output is correct
5 Correct 0 ms 4504 KB Output is correct
6 Correct 96 ms 5164 KB Output is correct
7 Correct 86 ms 5164 KB Output is correct
8 Correct 76 ms 5164 KB Output is correct
9 Correct 83 ms 4636 KB Output is correct
10 Correct 53 ms 10444 KB Output is correct
11 Correct 86 ms 6220 KB Output is correct
12 Correct 113 ms 7144 KB Output is correct
13 Correct 53 ms 4636 KB Output is correct
14 Correct 96 ms 6880 KB Output is correct
15 Correct 99 ms 17836 KB Output is correct
16 Correct 69 ms 10444 KB Output is correct
17 Correct 49 ms 4372 KB Output is correct
18 Correct 36 ms 4372 KB Output is correct