Submission #37026

#	Time	Username	Problem	Language	Result	Execution time	Memory
37026		DoanPhuDuc	Building Bridges (CEOI17_building)	C++98	100 / 100	113 ms	17836 KiB

building

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40