Submission #432955

#	Time	Username	Problem	Language	Result	Execution time	Memory
432955		yuto1115	Aliens (IOI16_aliens)	C++17	25 / 100	2083 ms	14476 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int inf = 1001001001;
const ll linf = 1001001001001001001;

// Convex Hull Trix (Minimum)
class li_chao_tree {
    int n;
    vl xs;
    // y = ax + b
    vl a, b;
    vi ls, rs;
    
    ll eval(ll na, ll nb, int x) {
        return na * xs[x] + nb;
    }
    
    void add(int k, ll na, ll nb) {
        int l = ls[k], r = rs[k], m = (l + r) / 2;
        if (l + 1 == r) {
            if (eval(a[k], b[k], l) > eval(na, nb, l)) {
                a[k] = na;
                b[k] = nb;
            }
            return;
        }
        if (eval(a[k], b[k], l) <= eval(na, nb, l) and eval(a[k], b[k], r) <= eval(na, nb, r)) return;
        if (eval(a[k], b[k], l) >= eval(na, nb, l) and eval(a[k], b[k], r) >= eval(na, nb, r)) {
            a[k] = na;
            b[k] = nb;
            return;
        }
        if (eval(a[k], b[k], m) > eval(na, nb, m)) {
            swap(a[k], na);
            swap(b[k], nb);
        }
        if (eval(a[k], b[k], l) > eval(na, nb, l)) {
            add(2 * k, na, nb);
            return;
        }
        if (eval(a[k], b[k], r) > eval(na, nb, r)) {
            add(2 * k + 1, na, nb);
            return;
        }
    }
    
    void init(const vl &_xs) {
        n = 1;
        while (n < (int) _xs.size()) n *= 2;
        a.assign(2 * n, 0);
        b.assign(2 * n, linf);
        ls.resize(2 * n);
        rs.resize(2 * n);
        rep(i, n) {
            ls[n + i] = i;
            rs[n + i] = i + 1;
        }
        rrep(i, n) {
            ls[i] = ls[2 * i];
            rs[i] = rs[2 * i + 1];
        }
        xs.resize(n + 1, _xs.back() + 1);
        rep(i, _xs.size()) xs[i] = _xs[i];
    }

public:
    li_chao_tree(const vl &_xs) {
        assert(is_sorted(all(xs)));
        init(_xs);
    }
    
    li_chao_tree(int n) {
        vl v(n);
        iota(all(v), 0);
        init(v);
    }
    
    ll get_min(int i) {
        assert(0 <= i and i < n);
        int x = i;
        i += n;
        ll res = linf;
        while (i >= 1) {
            chmin(res, eval(a[i], b[i], x));
            i >>= 1;
        }
        return res;
    }
    
    void add_line(ll na, ll nb) {
        add(1, na, nb);
    }
    
    void add_segment(int l, int r, ll na, ll nb) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        while (l < r) {
            if (l & 1) add(l++, na, nb);
            if (r & 1) add(--r, na, nb);
            l >>= 1, r >>= 1;
        }
    }
};

ll take_photos(int n, int m, int k, vi r, vi c) {
    vp v;
    rep(i, n) {
        if (r[i] <= c[i]) v.eb(r[i], c[i] + 1);
        else v.eb(c[i], r[i] + 1);
    }
    sort(all(v));
    vi ls;
    int mx = 0;
    rep(i, n) if (chmax(mx, v[i].second)) ls.pb(i);
    int sz = ls.size();
    vl s(sz), t(sz);
    rep(i, sz) {
        s[i] = v[ls[i]].first;
        t[i] = v[ls[i]].second;
    }
    vector<li_chao_tree> dp(k + 1, li_chao_tree(t));
    rep(i, sz) {
        dp[1].add_line(-2 * s[0], s[0] * s[0]);
    }
    rep2(i, 1, sz) rep2(j, 1, k) {
            ll now = dp[j].get_min(i - 1);
            if (now == linf) continue;
            now += t[i - 1] * t[i - 1];
            rep2(ni, i, sz) {
                ll lap = max(0LL, t[i - 1] - s[i]);
                dp[j + 1].add_line(-2 * s[i], now - lap * lap + s[i] * s[i]);
            }
        }
    ll ans = linf;
    rep2(i, 1, k + 1) chmin(ans, dp[i].get_min(sz - 1) + t.back() * t.back());
    return ans;
}

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