Submission #427532

#	Time	Username	Problem	Language	Result	Execution time	Memory
427532		timmyfeng	Aliens (IOI16_aliens)	C++17	100 / 100	614 ms	19956 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;

struct line {
    long long m, b, p;
};

long long offset[N], edge[N];

long long floor_div(long long a, long long b) {
    return a / b - ((a ^ b) < 0 && a % b != 0);
}

long long intersect(line a, line b) {
    return floor_div(a.b - b.b, b.m - a.m);
}

long long evaluate(line a, long long x) {
    return a.m * x + a.b;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    fill(edge, edge + m, -1);
    for (int i = 0; i < n; ++i) {
        if (r[i] > c[i]) {
            swap(r[i], c[i]);
        }
        edge[r[i]] = max(edge[r[i]], (long long) c[i]);
    }

    offset[0] = 1;
    for (int i = 1; i < m; ++i) {
        edge[i] = max(edge[i], edge[i - 1]);
        offset[i] = offset[i - 1] - 2 * i + 1;
    }

    long long ans = (long long) m * m;

    long long low = 0, high = ans;
    while (low < high) {
        long long mid = (low + high) / 2;

        long long cost = 0, photos = 0;
        deque<line> hull;

        int i = m - 1;
        for ( ; i >= 0 && edge[i] != -1; --i) {
            if (i == m - 1 || edge[i] != edge[i + 1]) {
                if (!hull.empty()) {
                    cost = evaluate(hull[0], i) - offset[i];
                    photos = hull[0].p;
                }

                int j = min(i, (int) edge[i]);
                line add = {-2 * edge[i], 2 * edge[i] * j + cost + mid + offset[j], photos + 1};
                while (hull.size() >= 2 && intersect(add, hull.back()) >= intersect(hull.back(), hull[hull.size() - 2])) {
                    hull.pop_back();
                }
                hull.push_back(add);
            }

            if (!hull.empty()) {
                while (hull.size() >= 2 && evaluate(hull[0], i - 1) > evaluate(hull[1], i - 1)) {
                    hull.pop_front();
                }
            }
        }

        cost = evaluate(hull[0], i) - (i == -1 ? 0 : offset[i]);
        photos = hull[0].p;

        if (photos <= k) {
            ans = cost - k * mid;
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    return ans;
}

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