Submission #275971

#	Time	Username	Problem	Language	Result	Execution time	Memory
275971		hamerin	Aliens (IOI16_aliens)	C++17	41 / 100	2107 ms	390520 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

const i64 inf = numeric_limits<i64>::max() / 3;

class Line {
   public:
    i64 a, b;

    Line() { a = 0, b = inf; }

    Line(i64 _a, i64 _b) { a = _a, b = _b; }

    inline i64 get(i64 x) { return a * x + b; }
};

class Node {
   public:
    i64 s, e;
    Line v;
    Node *l, *r;

    Node() {
        s = e = 0;
        v = Line();
        l = r = nullptr;
    }

    Node(i64 _s, i64 _e) {
        s = _s, e = _e;
        v = Line();
        l = r = nullptr;
    }

    Node(i64 _s, i64 _e, i64 _a, i64 _b) {
        s = _s, e = _e;
        v = Line(_a, _b);
        l = r = nullptr;
    }
};

namespace LiChao {
    Node* init(i64 s, i64 e) { return new Node(s, e); }

    void update(Node* here, const Line d) {
        i64 s = here->s, e = here->e;
        i64 m = (s + e) / 2;

        auto lo = here->v, hi = d;
        if (lo.get(s) > hi.get(s)) swap(lo, hi);

        if (lo.get(e) < hi.get(e)) {
            here->v = lo;
            return;
        }

        if (lo.get(m) < hi.get(m)) {
            here->v = lo;
            if (!here->r) here->r = new Node(m + 1, e);
            update(here->r, hi);
        } else {
            here->v = hi;
            if (!here->l) here->l = new Node(s, m);
            update(here->l, lo);
        }
    }

    i64 query(Node* here, const i64 x) {
        if (!here) return inf;

        i64 s = here->s, e = here->e;
        i64 m = (s + e) / 2;

        return min(here->v.get(x), x <= m ? query(here->l, x) : query(here->r, x));
    }
};  // namespace LiChao

inline i64 sq(const i64& x) {
    return x * x;
}

inline i64 sq(i64&& x) {
    return x * x;
}

i64 take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    vector<pi> cords(n);
    for (int i = 0; i < n; i++) cords[i] = {min(r[i], c[i]), max(r[i], c[i])};
    sort(iterall(cords), [](pi l, pi r) {
        return l.first == r.first ? l.second > r.second : l.first < r.first;
    });
    cords.erase(unique(iterall(cords)), cords.end());

    vector<i64> xc(1), yc(1);
    for (auto [x, y] : cords) {
        if (yc.size() == 1 || yc.back() < y) {
            xc.emplace_back(x);
            yc.emplace_back(y);
        }
    }
    for (auto& y : yc) ++y;

    const int N = xc.size() - 1;
    // for (int i = 1; i <= N; i++) cout << xc[i] << " " << yc[i] << endl;
    vector<Node*> roots(k + 1);
    for (int i = 0; i <= k; i++) roots[i] = LiChao::init(-1000001, 1000001);
    roots[0]->v.b = 0;

    vector<vector<i64>> D(N + 1, vector<i64>(k + 1, inf));
    for (int i = 1; i <= N; i++) {
        for (int j = k; j >= 1; j--) {
            if (j == 1) {
                D[i][j] = sq(yc[i] - xc[1]);
            } else {
                D[i][j] = sq(yc[i]) + LiChao::query(roots[j - 1], yc[i]);
            }

            // cout << i << " " << j << " " << D[i][j] << endl;
            if (i != N && D[i][j] < inf) {
                LiChao::update(roots[j],
                               Line(-2 * xc[i + 1],
                                    D[i][j] - sq(max(0LL, yc[i] - xc[i + 1])) + sq(xc[i + 1])));
            }
        }
    }

    i64 ret = inf;
    for (int j = 1; j <= k; j++) ret = min(ret, D[N][j]);

    return ret;
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40