Submission #995689

#	Time	Username	Problem	Language	Result	Execution time	Memory
995689		biank	Aliens (IOI16_aliens)	C++17	0 / 100	0 ms	348 KiB

aliens

#include<bits/stdc++.h>

using namespace std;

#define all(x) begin(x),end(x)
#define sz(x) int(x.size())

using ll = long long;
using ld = long double;

struct Line {
	ll m, b, k;
    mutable ld p; //we need to change p in the set
    Line(ll _m, ll _b, ll _k) : m(_m), b(_b), k(_k), p(0) {}
	bool operator<(const Line& o) const { //order by slope
        return m < o.m;
    }
	bool operator<(ld x) const {
        return p < x;
    }
    ld intersectX(const Line l) const {
        return ld(b - l.b) / (l.m - m);
    }
};

struct LineContainer : multiset<Line, less<>> {
	static constexpr ld INF = 1e18;
    bool intersect(iterator x, iterator y) {
        if (y == end()) {
            x->p = INF;
            return false;
        }
        if (x->m == y->m) { //parallel
            if (x->b > y->b) x->p = INF;
            else x->p = -INF;
        } else {
            x->p = x->intersectX(*y);
        }
        return x->p >= y->p;
    }
    void add(ll m, ll b, ll k) {
        auto next = emplace(m, b, k);
        auto prev = next, curr = next;
        next++;
 
        while (intersect(curr, next)) {
            next = erase(next);
        }
        
        if (prev != begin() && intersect(--prev, curr)) {
            curr = erase(curr);
            intersect(prev, curr);
        }
        curr = prev;
        while (curr != begin() && (--prev)->p >= curr->p) {
            curr = erase(curr);
            intersect(prev, curr);
            curr = prev;
        }
    }
	pair<ll, ll> query(ll x) {
		assert(!empty());
		Line l = *lower_bound(x);
		return {l.m * x + l.b, l.k};
	}
};

struct Point {
    ll x, y;
    Point(ll _x, ll _y) : x(_x), y(_y) {}
};

ll take_photos(int n, int /*m*/, int k, vector<int> r, vector<int> c){
    vector<Point> v;
    for (int i = 0; i < n; i++) {
        if (r[i] < c[i]) swap(r[i], c[i]);
        v.emplace_back(r[i], c[i]);
    }
    sort(all(v), [](const Point &a, const Point &b) {
        if (a.y != b.y) return a.y < b.y;
        return a.x > b.x;
    });
    vector<Point> p{v[0]};
    for (int i = 1; i < n; i++) {
        if (p.back().x < v[i].x) p.push_back(v[i]);
    }
    n = sz(p);
    k = min(k, n);
    auto sq = [](ll x) { return x * x; };
    auto check = [&](ll lambda) {
        LineContainer dp;
        ll res = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            ll m = -2LL * (p[i].y - 1LL);
            ll b = res + sq(p[i].y - 1LL);
            if (i > 0) b -= sq(max(p[i - 1].x - p[i].y + 1LL, 0LL));
            dp.add(m, b, cnt);
            tie(res, cnt) = dp.query(p[i].x);
            res += sq(p[i].x) + lambda, cnt++;
        }
        return pair<ll, ll>{res, cnt};
    };
    ll lo = 0, hi = 1e13;
    while (hi - lo > 1) {
        ll mid = (hi - lo) / 2 + lo;
        if (check(mid).second <= k) hi = mid;
        else lo = mid;
    }
    return check(hi).first - k * hi;
}

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