Submission #830036

#	Time	Username	Problem	Language	Result	Execution time	Memory
830036		rembocoder	Aliens (IOI16_aliens)	C++17	25 / 100	1 ms	468 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
    if (a.first != b.first) {
        return a.first < b.first;
    }
    return a.second > b.second;
}

const long long inf = 2e18;

long long div_up(long long a, long long b) {
    if (a < 0) {
        return a / b;
    }
    return (a + b - 1) / b;
}

long long take_photos(int n, int m, int k, vector<int> x, vector<int> y) {
    for (int i = 0; i < n; i++) {
        if (x[i] > y[i]) {
            swap(x[i], y[i]);
        }
    }
    vector<pair<int, int>> pairs;
    for (int i = 0; i < n; i++) {
        pairs.push_back({x[i], y[i]});
    }
    sort(pairs.begin(), pairs.end(), cmp);
    vector<pair<int, int>> new_pairs;
    new_pairs.push_back({-1, -1});
    int max_y = -1;
    for (int i = 0; i < n; i++) {
        if (max_y < pairs[i].second) {
            max_y = pairs[i].second;
            new_pairs.push_back(pairs[i]);
        }
    }
    n = new_pairs.size();
    vector<long long> l(n), r(n);
    for (int i = 0; i < n; i++) {
        l[i] = new_pairs[i].first;
        r[i] = new_pairs[i].second + 1;
    }
    k = min(k, n - 1);

    auto ans = [&](int lambda) -> pair<long long, int> {
        vector<pair<long long, int>> dp(n, {inf, -1});
        dp[0] = {0, 0};
        vector<long long> a(n), b(n);

        auto count_ab = [&](int i) -> void {
            a[i] = dp[i].first + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
            b[i] = 2 * l[i + 1];
        };

        vector<pair<long long, int>> ch;
        count_ab(0);
        ch.push_back({-1, 0});
        int ch_from = 0;
        for (int i = 1; i < n; i++) {
            while (ch_from + 1 < ch.size() && ch[ch_from + 1].first <= r[i]) {
                ch_from++;
            }
            int from = ch[ch_from].second;
            dp[i] = {r[i] * r[i] + a[from] - b[from] * r[i] + lambda, dp[from].second + 1};
            if (i + 1 == n) {
                break;
            }
            count_ab(i);
            while (!ch.empty()) {
                int last = ch.back().second;
                long long x = ch.back().first;
                if (a[last] - b[last] * x < a[i] - b[i] * x ||
                    a[last] - b[last] * x == a[i] - b[i] * x && dp[last].second < dp[i].second) {
                    break;
                }
                ch.pop_back();
            }
            int last = ch.back().second;
            long long x = div_up(a[i] - a[last], b[i] - b[last]);
            if (x == ch.back().first) {
                x++;
            }
            ch.push_back({x, i});
            if (ch_from >= ch.size()) {
                ch_from = ch.size() - 1;
            }
        }
        return dp.back();
    };

    int l_bin = -1, r_bin = m * m;
    while (r_bin - l_bin > 1) {
        int mid = (l_bin + r_bin) / 2;
        if (ans(mid).second <= k) {
            r_bin = mid;
        } else {
            l_bin = mid;
        }
    }
    int lambda = r_bin;
    pair<long long, int> res = ans(lambda);
    return res.first - res.second * lambda - (k - res.second) * (lambda - 1);
}

Compilation message (stderr)

aliens.cpp: In lambda function:
aliens.cpp:65:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             while (ch_from + 1 < ch.size() && ch[ch_from + 1].first <= r[i]) {
      |                    ~~~~~~~~~~~~^~~~~~~~~~~
aliens.cpp:78:62: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   78 |                     a[last] - b[last] * x == a[i] - b[i] * x && dp[last].second < dp[i].second) {
aliens.cpp:89:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             if (ch_from >= ch.size()) {
      |                 ~~~~~~~~^~~~~~~~~~~~

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