Submission #1087640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087640		dyc123	Aliens (IOI16_aliens)	C++17	0 / 100	2069 ms	352 KiB

aliens

#pragma once

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

typedef long long ll;

typedef std::complex<ll> point;
#define x real
#define y imag

const ll INF = 1e18;

//imagine overflowing smh smh
ll dot(point a, point b) {
    return (std::conj(a) * b).x();
}

ll cross(point a, point b) {
    return (std::conj(a) * b).y();
}

std::vector<point> hull, vecs;
std::vector<int> cnth;

void add_line(ll slope, ll y_intercept, int cnt) {
    point new_line({slope, y_intercept});
    while(!vecs.empty() && dot(vecs.back(), new_line - hull.back()) < 0) {
        hull.pop_back();
        vecs.pop_back();
        cnth.pop_back();
    }
    if(!hull.empty()) {
        vecs.push_back(point({0, 1}) * (new_line - hull.back()));
    }
    hull.push_back(new_line);
    cnth.push_back(cnt);
}

pair<ll, int> get(ll x_value) {
    point to_query = point({x_value, 1});
    int index = lower_bound(vecs.begin(), vecs.end(), to_query, [](point a, point b) {
        return cross(a, b) > 0;
    }) - vecs.begin();
    return {dot(to_query, hull[index]), cnth[index]};
}

long long take_photos(int n, int m, int k, std::vector<int> rr, std::vector<int> cc) {
    vector<array<int, 2>> intervals;
    for(int i = 0; i < n; i++) {
        if(rr[i] > cc[i]) swap(rr[i], cc[i]);
        intervals.push_back({rr[i], cc[i]});
    }
    sort(intervals.begin(), intervals.end(), [](array<int, 2> a, array<int, 2> b) {
        if(a[0] == b[0]) return a[1] > b[1];
        return a[0] < b[0];
    });

    // TODO: remove overlapping intervals
    vector<ll> l, r;
    for(int i = 0; i < n; i++) {
        if(i == 0 || intervals[i - 1][0] > intervals[i][0] || intervals[i - 1][1] < intervals[i][1]) {
            l.push_back(intervals[i][0]);
            r.push_back(intervals[i][1]);
        }
    }
    
    n = l.size();

    auto works = [&](ll lambda, ll& ans) {
        hull.clear();
        vecs.clear();
        cnth.clear();
        vector<ll> dp(n + 1, INF);
        vector<int> cnt(n + 1);
        dp[0] = 0;
        for(int i = 1, j = 0; i <= n; i++, j++) {
            ll slope = 2 * l[j];
            ll intercept = (l[j] * l[j] - 2 * l[j] + dp[j]);
            if(j > 0) {
                ll mx = max(0LL, r[j - 1] - l[j] + 1);
                intercept -= mx * mx;
            }
            add_line(slope, intercept, cnt[i]);
            auto gg = get(-r[j]);
            dp[i] = gg.first + (r[j] + 1) * (r[j] + 1) + lambda;
            cnt[i] = gg.second + 1;
        }
        ans = dp[n];
        return cnt[n] >= k;
    };
    ll lo = 0, hi = INF, ans = INF;
    while(lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        if(works(mid, ans)) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    return ans - k * lo;
}

Compilation message (stderr)

aliens.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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