Submission #1230796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230796		changhw	Aliens (IOI16_aliens)	C++20	4 / 100	5 ms	8264 KiB

aliens

#include <bits/stdc++.h>

using namespace std;
#define fastio ios::sync_with_stdio(false), cin.tie(NULL)
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod = 1e9 + 7;

// convex hull trick
struct CHT{
    // y = ax + b
    struct line{
        ll a, b, cnt;
        ll eval(ll x) const {
            return a*x + b;
        }
    };

    deque<line> dq;

    // a와 b의 교점이 c의 교점보다 오른쪽에 있으면 true
    static bool chk(line l1, line l2, line l3){
        return (l2.b - l1.b) * (l1.a - l3.a) >= (l3.b - l1.b) * (l1.a - l2.a);
    }

    void insert(ll a, ll b, ll cnt){
        line l = {a, b, cnt};
        while(dq.size() >= 2 && chk(dq[dq.size() - 2], dq[dq.size() - 1], l))
            dq.pop_back();

        dq.push_back(l);
    }

    pll query(ll x){
        while(dq.size() >= 2 && dq[0].eval(x) >= dq[1].eval(x))
            dq.pop_front();
        return {dq[0].eval(x), dq[0].cnt};
    }
};

const ll INF = 1e18;
vector<pll> points;

// alien trick
vector<ll> dp(505050), cdp(505050);

ll cost(ll x){
    ll ret = points[x+1].first * points[x+1].first;
    if(x != -1) {
        ll tmp = max(points[x].second - points[x + 1].first + 1, 0LL);
        ret -= tmp * tmp;
    }
    return ret;
}

void solve(ll d){
    ll n = points.size();
    CHT cht;
    ll a = -2 * points[0].first;
    ll b = cost(-1) + d;
    cht.insert(a, b, 0);
    for(int i = 0; i < n; i++){
        auto [val, cnt] = cht.query(points[i].second + 1);
        dp[i] = val + (points[i].second + 1) * (points[i].second + 1);
        cdp[i] = cnt + 1;

        if(i == n-1) break;
        a = -2 * points[i+1].first;
        b = cost(i) + dp[i] + d;
        cht.insert(a, b, cdp[i]);
    }
}


ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    for(int i = 0; i < n; i++){
        int x = r[i], y = c[i];
        if(x > y) swap(x, y);
        points.emplace_back(x, y);
    }

    sort(points.begin(), points.end());

    vector<pll> tp;
    tp.push_back(points[0]);
    for(int i = 1; i < n; i++){
        while(!tp.empty() && tp.back().first == points[i].first)
            tp.pop_back();

        if(tp.empty() || tp.back().second < points[i].second)
            tp.push_back(points[i]);
    }
    points = tp;

//    for(auto [x, y] : points){
//         cout << x << ' ' << y << endl;
//    }

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

    ll d = 0;
    ll ans = 1e18;
    ll begin = 0, end = 1e13;
    while(begin <= end){
        ll mid = (begin + end) >> 1;
        solve(mid);
        if(cdp[n-1] <= k){
            d = mid;
            end = mid - 1;
        } else {
            begin = mid + 1;
        }
    }

    solve(d);
    ans = dp[n-1] - k * d;
    return ans;
}

// int main() {
//     fastio;
//     int n, m, k;
//     cin >> n >> m >> k;
//     vector<int> r(n), c(n);
//     for(int i = 0; i < n; i++)
//         cin >> r[i] >> c[i];

//     cout << take_photos(n, m, k, r, c);
//     return 0;
// }

Compilation message (stderr)

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

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