Submission #1082651

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

aliens

#include "aliens.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 1e6 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

struct line {
    ll m, c;
    ll eval (ll x) { return m * x + c; }
    ld its (line l) { return (ld) (c - l.c) / (l.m - m); }
};

ll sqr (ll x){
    return x * x;
}

ll dp[N], cnt[N];
vector <pll> v;
map <ll, ll> z;

void calc (ll x){
    deque <line> dq;
    deque <int> dqcnt;
    dq.push_front({-2 * v[0].st, x + 1 + sqr(v[0].st) - 2 * v[0].st});
    dqcnt.push_front(0);
    
    forf (i, 0, v.size()){
        while (dq.size() >= 2 && dq.back().eval(v[i].nd) > dq[dq.size() - 2].eval(v[i].nd)){
            dq.pop_back();
            dqcnt.pop_back();
        }
    
        dp[i] = dq.back().eval(v[i].nd) + sqr(v[i].nd) + 2 * v[i].nd;
        cnt[i] = cnt[dqcnt.back()] + 1;

        line cur = {-2 * v[i].st, dp[i] + x + 1 - sqr(max(0ll, v[i].nd - v[i + 1].st + 1)) 
            + sqr(v[i + 1].st) - 2 * v[i + 1].st};

        while (dq.size() >= 2 && cur.its(dq[0]) >= dq[0].its(dq[1]))
            dq.pop_front();
        dq.push_front(cur);
    }
}

ll take_photos (int n, int m, int k, int r[], int c[]){
    forf (i, 0, n){
        if (r[i] > c[i]) swap(r[i], c[i]);
        maxz(z[r[i]], c[i]);
    }

    ll mx = 0;
    for (pll t : z){
        if (t.nd > mx){
            v.pb(t);
            mx = t.nd;
        }
    }
    
    ll l = 0, h = 1ll * m * m;
    n = v.size() - 1;

    // for (pii t : v)
    //     cout << t.st << " " << t.nd << "\n";

    while (l < h){
        ll mid = (l + h) >> 1;
        calc(mid);
        //cout << mid << " " << cnt[n] << endl;
        if (cnt[n] > k)
            l = mid + 1;
        else h = mid;
    } 

    calc(l);

    //cout << dp[n] << " " << cnt[n] << " " << l << endl;; 
    
    return dp[n] - k * l;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccdiqdDq.o: in function `main':
grader.cpp:(.text.startup+0xf0): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status