Submission #162841

#	Time	Username	Problem	Language	Result	Execution time	Memory
162841		rama_pang	Aliens (IOI16_aliens)	C++14	100 / 100	223 ms	11444 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e15;

struct Segment {
    lint left, right;

    Segment(lint l = 0, lint r = 0): left(l), right(r) {}

    bool operator < (const Segment &o) const {
        return left < o.left || (left == o.left && right > o.right);
    }

    bool operator == (const Segment &o) const {
        return left == o.left && right == o.right;
    }

};

struct ConvexHull { // Convex Hull Trick
    struct Line {
        lint m, c;
        int cnt;

        Line(lint M = 0, lint C = INF, int cnt_ = 0): m(M), c(C), cnt(cnt_) {}

        lint get(lint x) {
            return m * x + c;
        }

    };

    vector<Line> hull = {Line(0, INF)};

    int ptr = 0;

    void insert(lint m, lint c, int cnt) {
        hull.emplace_back(Line(m, c, cnt));
        int sz = hull.size() - 1;

        while (ptr <= sz - 2 && (hull[sz - 1].c - hull[sz].c) * (hull[sz - 1].m - hull[sz - 2].m) < 
                                (hull[sz - 2].c - hull[sz - 1].c) * (hull[sz].m - hull[sz - 1].m)) 
            hull[sz - 1] = hull[sz], sz--, hull.pop_back();

    }

    lint query(lint x) {
        while (ptr + 1 < hull.size() && hull[ptr].get(x) > hull[ptr + 1].get(x))
            ptr++;

        return hull[ptr].get(x) + x * x;
    }

    int cnt_query(lint x) {
        query(x);
        return hull[ptr].cnt;
    }

    void clear() {
        hull.clear();
        hull = {Line(0, INF)};
        ptr = 0;
    }

};

int N, K;
vector<Segment> segment;
vector<lint> DP; // find optimal answer in O(N)
vector<int> cnt; // K used in DP[i] (optimal)
ConvexHull hull;

void preprocess(int n, int k, vector<int> r, vector<int> c) {
    for (int i = 0; i < n; i++) 
        segment.emplace_back(min(r[i], c[i]), max(r[i], c[i]));

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

    vector<Segment> tmp;
    tmp.emplace_back(-1, -1);
    
    for (auto s : segment) {
        Segment overlap = Segment(min(tmp.back().left, s.left), max(tmp.back().right, s.right));
        if (overlap == s) swap(s, tmp.back());
        if (overlap == tmp.back()) continue;
        tmp.emplace_back(s);
    }

    segment = tmp, N = segment.size() - 1, K = k;
    DP.assign(N + 1, 0), cnt.assign(N + 1, 0);
}

void computeDP(lint lambda) { // returns number of k used, with each photo having penalty lambda (equals to DP[N][K] + K * lambda)
    DP[0] = cnt[0] = 0, hull.clear();

    for (int n = 1; n <= N; n++) {
        lint m = - 2 * segment[n].left;
        lint c = + segment[n].left * segment[n].left 
                 - max(0ll, segment[n - 1].right - segment[n].left + 1) * 
                   max(0ll, segment[n - 1].right - segment[n].left + 1)
                 + DP[n - 1] + lambda;

        hull.insert(m, c, cnt[n - 1] + 1);

        cnt[n] = hull.cnt_query(segment[n].right + 1);
        DP[n]  = hull.query(segment[n].right + 1);
    }

}

lint take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    lint opt = INF;
    preprocess(n, k, r, c);

    for (lint le = 0, ri = INF, mid = (le + ri) / 2; le <= ri; mid = (le + ri) / 2) {
        computeDP(mid);
        if (cnt[N] <= K)
            ri = mid - 1, opt = mid;
        else
            le = mid + 1;
    }

    computeDP(opt);
    return DP[N] - K * opt;
}

Compilation message (stderr)

aliens.cpp: In member function 'lint ConvexHull::query(lint)':
aliens.cpp:50:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (ptr + 1 < hull.size() && hull[ptr].get(x) > hull[ptr + 1].get(x))
                ~~~~~~~~^~~~~~~~~~~~~

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