Submission #419949

#	Time	Username	Problem	Language	Result	Execution time	Memory
419949		jhnah917	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KiB

aliens

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using PLL = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;

inline ll sq(ll v){ return v*v; }

struct Line{
    ll a, b, i;
    Line() : Line(0, INF, 0) {}
    Line(ll a, ll b, ll i) : a(a), b(b), i(i) {}
    ll f(ll x) const { return a * x + b; }
};

struct CHT{
    vector<Line> lines;
    int pv;
    void clear(){ lines.clear(); pv = 0; }
    int __cross(const Line &a, const Line &b, const Line &c){
        return (__int128_t)(a.b - b.b) * (b.a - c.a) <= (__int128_t)(c.b - b.b) * (b.a - a.a);
    }
    void update(const Line l){
        while(lines.size() >= 2 && __cross(lines[lines.size()-2], lines.back(), l)) lines.pop_back();
        lines.push_back(l);
    }
    PLL query(ll x){
        while(pv+1 < lines.size() && lines[pv].f(x) >= lines[pv+1].f(x)) pv++;
        return {lines[pv].f(x), lines[pv].i};
    }
} cht;

int N, K;
PLL A[101010];
ll D[101010], C[101010];

void init(int _n, int _m, int _k, const vector<int> &_r, const vector<int> &_c){
    K = _k;
    vector<PLL> pts;
    for(int i=0; i<_n; i++) pts.emplace_back(min(_r[i], _c[i]), max(_r[i], _c[i]));
    sort(all(pts));
    for(const auto &i : pts){
        while(N && A[N].y >= i.y) N--;
        A[++N] = i;
    }
}

Line makeLine(ll i){
    ll a = -2*A[i+1].x, b = D[i] + sq(A[i+1].x) - 2*A[i+1].x;
    if(i) b -= sq(max(0LL, A[i].y-A[i+1].x+1));
    return Line(a, b, i);
}

ll get(ll c){
    cht.clear();
    cht.update(makeLine(0));
    for(int i=1; i<=N; i++){
        auto res = cht.query(A[i].y);
        D[i] = res.x + sq(A[i].y+1) + c;
        C[i] = res.y;
        cht.update(makeLine(i));
    }
    return C[N];
}

ll take_photos(int _n, int _m, int _k, vector<int> _r, vector<int> _c){
    init(_n, _m, _k, _r, _c);
    int X = min(N, K);

    ll l = 0, r = 1e15;
    while(l < r){
        ll m = l + r >> 1, cnt = get(m);
        if(cnt == X) return D[N] - X*m;
        else if(cnt < X) r = m;
        else l = m + 1;
    }
    get(r);
    return D[N] - X*r;
}

int main(){
    int n, m, k; cin >> n >> m >> k;
    vector<int> r(n), c(n);
    for(int i=0; i<n; i++) cin >> r[i] >> c[i];
    cout << take_photos(n, m, k, r, c);
}

Compilation message (stderr)

aliens.cpp: In member function 'PLL CHT::query(ll)':
aliens.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         while(pv+1 < lines.size() && lines[pv].f(x) >= lines[pv+1].f(x)) pv++;
      |               ~~~~~^~~~~~~~~~~~~~
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:75:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         ll m = l + r >> 1, cnt = get(m);
      |                ~~^~~
/usr/bin/ld: /tmp/ccOvRiQJ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc2YBpTJ.o:aliens.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status