Submission #1198801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198801		ericl23302	Aliens (IOI16_aliens)	C++20	100 / 100	151 ms	11068 KiB

aliens

#include "aliens.h"

#include <iostream>
#include <algorithm>
#include <utility>
#include <climits>
#include <complex>
// using namespace std;
// using ll = long long;

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

// ll sq(ll a) {
//     return a * a;
// }
// ll sq(int a) {
//     return (ll)(a) * a;
// }

// // ll getArea(pair<ll, ll> a) {
// //     return sq(a.second - a.first + 1);
// // }
// // ll getArea(ll a, ll b) {
// //     return sq(b - a + 1);
// // }

// ll positiveArea(ll a, ll b) {
//     ll sideLength = b - a + 1;
//     return (sideLength > 0 ? sq(sideLength) : 0);
// }

// ll dot(point a, point b) {
//     return ((conj(a) * b).x());
// }

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

// vector<point> hull, vec;
// vector<ll> countHull;

// void addLine(ll m, ll c, ll count) {
//     point newLine({m, c});
//     while (!vec.empty() && (dot(vec.back(), newLine - hull.back()) < 0)) {
//         vec.pop_back();
//         hull.pop_back();
//         countHull.pop_back();
//     }
//     if (!hull.empty()) vec.push_back(point({0, 1}) * (newLine - hull.back()));
//     countHull.push_back(count);
//     hull.push_back(newLine);
// }

// pair<ll, ll> query(ll ri) {
//     point toFind({ri, 1});
//     ll idx = lower_bound(vec.begin(), vec.end(), toFind, [](point a, point b) {return (cross(a, b) > 0);}) - vec.begin();
//     return {dot(toFind, hull[idx]), countHull[idx]};
// }

// ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
//     vector<pair<ll, ll>> oriPoints, points;
//     for (ll i = 0; i < n; ++i) {
//         if (r[i] > c[i]) swap(r[i], c[i]);
//         oriPoints.emplace_back(r[i], c[i]);
//     }
//     sort(oriPoints.begin(), oriPoints.end());
    
//     pair<ll, ll> cur = oriPoints[0];
//     for (ll i = 1; i < n; ++i) {
//         if (oriPoints[i].first == cur.first) cur.second = max(oriPoints[i].second, cur.second);
//         else if (cur.second < oriPoints[i].second) {
//             if (cur.first != -1) points.emplace_back(cur);
//             cur = oriPoints[i];
//         }
//     }
//     points.emplace_back(cur);
//     int newN = points.size();


//     auto check = [&] (ll cost, ll &res) {
//         hull.clear(); vec.clear(); countHull.clear();
//         vector<ll> dp(newN + 1, 0), counts(newN + 1, 0);
//         for (int i = 1; i <= newN; ++i) {
//             ll m = 2 * (points[i - 1].first - 1), c = sq(points[i - 1].first - 1) + dp[i - 1] + (i > 1 ? positiveArea(points[i - 1].first, points[i - 2].second) : 0);
//             addLine(m, c, counts[i - 1]);
//             auto cur = query(-points[i - 1].second);
//             dp[i] = cur.first + cost + sq(points[i - 1].second);
//             counts[i] = cur.second + 1;
//         }
//         res = dp[newN];
//         return (counts[newN] <= k);
//     };

//     ll low = 0, high = sq(m), res = LLONG_MAX / 2;
//     while (low < high) {
//         ll mid = (low + high) / 2;
//         if (check(mid, res)) high = mid;
//         else low = mid + 1;
//     }
//     check(low, res);
    
//     return (res - k * low);
// }
using namespace std;

typedef long long ll;

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

const ll INF = 1e18;

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();
    ll val = dot(to_query, hull[index]);
    int mx = cnth[index];
    return {val, mx};
}

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];
    });

    vector<array<int, 2>> intervals2;
    vector<ll> l, r;
    for(int i = 0; i < n; i++) {
        if(i == 0 || intervals[i][0] < intervals2.back()[0] || intervals[i][1] > intervals2.back()[1]) {
            intervals2.push_back(intervals[i]);
            l.push_back(intervals[i][0]);
            r.push_back(intervals[i][1]);
        }
    }
    n = intervals2.size();

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

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: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40