Submission #731806

#	Time	Username	Problem	Language	Result	Execution time	Memory
731806		vjudge1	Aliens (IOI16_aliens)	C++11	25 / 100	2095 ms	666568 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>
using namespace std;

vector<int> query_points;
class lichaotree_t {
       public:
        class line_t {
               public:
                int64_t a, b;
                line_t(int64_t a = 0, int64_t b = 0) : a(a), b(b) {}
                int64_t operator()(const int64_t &x) const {
                        return a * x + b;
                }
        };
        lichaotree_t *left, *right;
        line_t line;
        int l, r, m;
        lichaotree_t(int l = 0, int r = query_points.size() - 1) : line(0, 9e18) {
                int m = l + r >> 1;
                this->l = query_points[l];
                this->r = query_points[r];
                this->m = query_points[m];
                if (l == r) return;
                left = new lichaotree_t(l, m);
                right = new lichaotree_t(m + 1, r);
        }

        void insert(int64_t a, int64_t b) {
                line_t newline(a, b);
                bool better_l = line(l) >= newline(l);
                bool better_r = line(r) >= newline(r);
                if (better_l && better_r) {
                        line = newline;
                        return;
                } else if (better_l || better_r) {
                        left->insert(a, b);
                        right->insert(a, b);
                }
        }

        int64_t get_min(int64_t x) {
                if (l == r) return line(x);
                if (x <= m) {
                        return min(line(x), left->get_min(x));
                } else {
                        return min(line(x), right->get_min(x));
                }
        }
};

long long take_photos(int n, int m, int k, std::vector<int> a, std::vector<int> b) {
        for (int i = 0; i < n; i++) {
                if (a[i] > b[i]) swap(a[i], b[i]);
        }
        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
                return a[i] == a[j] ? b[i] > b[j] : a[i] < a[j];
        });
        vector<int> l, r;
        int last = -1;
        for (int i = 0; i < n; i++) {
                if (b[ord[i]] <= last) continue;
                l.emplace_back(a[ord[i]] - 1);
                r.emplace_back(b[ord[i]]);
                last = b[ord[i]];
        }

        n = l.size();
        k = min(k, n);

        auto cost = [](int l, int r) {
                if (l > r) return 0ll;
                return 1ll * (r - l) * (r - l);
        };

        for (int i = 0; i < n; i++) query_points.emplace_back(r[i]);
        lichaotree_t *tree[k - 1];
        for (int i = 0; i < k - 1; i++) tree[i] = new lichaotree_t();

        int64_t f;

        for (int i = 0; i < n; i++) {
                for (int j = min(i, k - 1); j >= 0; j--) {
                        if (i + k - j > n) continue;
                        f = j ? tree[j - 1]->get_min(r[i]) + 1ll * r[i] * r[i] : cost(l[0], r[i]);
                        if (i + 1 < n && j != k - 1) tree[j]->insert(-2 * l[i + 1], f + 1ll * l[i + 1] * l[i + 1] - cost(l[i + 1], r[i]));
                }
        }

        return f;
}

Compilation message (stderr)

aliens.cpp: In constructor 'lichaotree_t::lichaotree_t(int, int)':
aliens.cpp:21:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |                 int m = l + r >> 1;
      |                         ~~^~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:93:16: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |         return f;
      |                ^

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