Submission #500480

#	Time	Username	Problem	Language	Result	Execution time	Memory
500480		dooompy	Aliens (IOI16_aliens)	C++17	100 / 100	192 ms	13368 KiB

aliens

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

using namespace std;


template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

#define ll long long

//struct line {
//    ll m, c; int id;
//
//    ll eval(ll x) {
//        return m * x + c;
//    }
//
//    long double intersectX(line o) const {
//        return (long double) (c - o.c) / (o.m - m);
//    }
//};


struct line {
    ll a, b, i;
    line(ll a=0, ll b=0, ll i=0) : a(a), b(b), i(i) {}
    ll calc(ll x) { return a*x+b;}
    double inter(line l) {
        return double(l.b - b) / (a - l.a);
    }
};
bool check_back_pd(line& p0, line& p1, line& p2) {
    return p0.inter(p1) > p1.inter(p2);
}
bool check_back(line& p0, line& p1, line& p2) {
    return (p1.b - p0.b) * (p1.a - p2.a) >= (p0.a - p1.a) * (p2.b - p1.b);
}
bool check_front_pd(ll x, line& p0, line& p1) {
    return x > p0.inter(p1);
}
bool check_front(ll x, line& p0, line& p1) {
    return x * (p0.a - p1.a) >= (p1.b - p0.b);
}

using pll = pair<ll, ll>;

struct ConvexHull {
    size_t apos = 0;
    vector<line> v;
    void insert(line p) {
        while(1) {
            size_t sz = v.size();
            if(sz - apos >= 2 && check_back_pd(v[sz-2], v[sz-1], p)) {
                v.pop_back();
                sz--;
            }
            else break;
        }
        v.push_back(p);
    }
    pll query(ll x) {
        while(1) {
            size_t sz = v.size();
            if(sz - apos >= 2 && check_front_pd(x, v[apos], v[apos+1]))
                apos++;
            else break;
        }
        return pll{v[apos].calc(x), v[apos].i};
    }
};



vector<pair<ll, ll>> points;

pair<ll, ll> ct(ll c) {
//    deque<line> dq;

//    dq.push_back({-2 * points[0].first, points[0].first * points[0].first - 2  * points[0].first, 0});

    ConvexHull dq;

    dq.insert({-2 * points[0].first, points[0].first * points[0].first - 2  * points[0].first, 0});

    ll n = points.size();
    vector<ll> ct(n + 5);
    vector<ll> dp(n + 5);

    ll total = 0;

    for (int i = 0; i < n; i++) {
//        while (dq.size() >= 2 && dq[0].eval(points[i].second) >= dq[1].eval(points[i].second)) dq.pop_front();

//        ll cur = dq.front().eval(points[i].second) + (points[i].second + 1) * (points[i].second + 1) + c;
        auto temp = dq.query(points[i].second);
        ll cur = temp.first + (points[i].second + 1) * (points[i].second + 1) + c;
        dp[i] = cur;
        total = temp.second + 1;
        ct[i + 1] = ct[temp.second] + 1;
//        ct[i + 1] = ct[dq.front().id] + 1;

        if (i == n-1) break;

        line l = {-2 * points[i+1].first, points[i + 1].first * points[i + 1].first - 2 * points[i + 1].first + dp[i] - max(points[i].second - points[i + 1].first + 1, 0LL) * max(points[i].second - points[i + 1].first + 1, 0LL), total};

        dq.insert(l);
//        while (dq.size() >= 2 && l.intersectX(dq.back()) <= dq.back().intersectX(dq[dq.size() - 2])) dq.pop_back();
//        dq.push_back(l);
    }

    return {total, dp[n-1]};
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {

    for (int i = 0; i < n; i++) {
        if (r[i] > c[i]) swap(r[i], c[i]);
        points.emplace_back(r[i], c[i]);
    }

    sort(points.begin(), points.end(), [](pair<int, int> a, pair<int, int> b) {
        if (a.second == b.second) {
            return a.first > b.first;
        } else return a.second < b.second;
    });

    vector<pair<ll, ll>> final;

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

    }

    points = final;

    test(points);

    ll left = 0, right = 1e13;

    while (left != right) {
        ll mid = (left + right) / 2;
        auto cur = ct(mid);
//        if (cur.first == k) return cur.second - mid * k;
        if (cur.first > k) left = mid + 1;
        else right = mid;
    }

    test(left, k);

    auto ans = ct(left);

    test(ans);

    return ans.second  - left * (ll) k;
}

//int main() {
//    take_photos(2, 2, 1, {0, 1}, {0, 1});
//
//}

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