Submission #748559

#	Time	Username	Problem	Language	Result	Execution time	Memory
748559		AnhPham	Aliens (IOI16_aliens)	C++17	100 / 100	147 ms	12988 KiB

aliens

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

#define long long long
#define pii pair<long, long>
#define x first
#define y second

using namespace std;

struct cht {
    struct line {
        long m, b;
        int cnt;
        line(long m, long b, int cnt) : m(m), b(b), cnt(cnt) {}
        long get(long x) { return m * x + b; }
    };
    vector<line> f;
    int ptr = 0;
    bool bad(line a, line b, line c) {
        return (c.b - a.b) * (a.m - b.m) <= (b.b - a.b) * (a.m - c.m);
    }
    void add(long m, long b, int cnt) {
        line l(m, b, cnt);
        while (f.size() >= 2 && bad(f[f.size() - 2], f.back(), l))
            f.pop_back();
        f.emplace_back(l);
    }
    pii query(long x) {
        while (ptr + 1 < f.size() && f[ptr + 1].get(x) < f[ptr].get(x))
            ++ptr;
        return pii(f[ptr].get(x), f[ptr].cnt);
    }
    void clear() { f.clear(), ptr = 0; }
} hull;

int n;
long mx = 0;
vector<long> l = {-1}, r = {-1};

long sq(long a) { return a * a; }

pii solve(long C) {
    vector<pii> dp = vector<pii>(n + 1);
    hull.clear();
    dp[0] = {0, 0};
    hull.add(-2ll * (l[1] - 1), sq(l[1] - 1), 0);
    for (int i = 1; i <= n; i++) {
        pii now = hull.query(r[i]);
        dp[i] = pii(now.x + sq(r[i]) + C, now.y + 1);
        if (i == n)
            continue;
        hull.add(-2ll * (l[i + 1] - 1),
                 sq(l[i + 1] - 1) + dp[i].x - sq(max(0ll, r[i] - l[i + 1] + 1)),
                 dp[i].y);
    }
    return dp[n];
}

long take_photos(int _n, int _m, int k, vector<int> _r, vector<int> _c) {
    vector<pii> coord;
    for (int i = 0; i < _n; i++) {
        if (_r[i] > _c[i])
            swap(_r[i], _c[i]);
        coord.emplace_back(_c[i], _r[i]);
    }
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    for (pii p : coord) {
        if (p.x == r.back())
            continue;
        while (!l.empty() && p.x >= r.back() && p.y <= l.back())
            l.pop_back(), r.pop_back();
        l.emplace_back(p.y), r.emplace_back(p.x);
    }
    n = l.size() - 1;
    k = min(k, n);
    long a = 0, b = 1e17;
    while (a < b) {
        long mid = (a + b) >> 1;
        if (solve(mid).y <= k)
            b = mid;
        else
            a = mid + 1;
    }
    return solve(b).x - b * k;
}

Compilation message (stderr)

aliens.cpp: In member function 'std::pair<long long int, long long int> cht::query(long long int)':
aliens.cpp:30:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cht::line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         while (ptr + 1 < f.size() && f[ptr + 1].get(x) < f[ptr].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