Submission #1227772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227772		madamadam3	Aliens (IOI16_aliens)	C++20	100 / 100	1016 ms	161256 KiB

aliens

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

using namespace std;

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

const ll INF = 1e18;

int n, m, k;
vl r, c, L, R;

void preprocess(int N, int M, int K, vi Row, vi Col) {
    vector<int> sorted_points(N); iota(sorted_points.begin(), sorted_points.end(), 0);
    sort(sorted_points.begin(), sorted_points.end(), [&](int a, int b) {
        ll La = min(Row[a], Col[a]), Ra = max(Row[a], Col[a]), Lb = min(Row[b], Col[b]), Rb = max(Row[b], Col[b]);
        return La == Lb ? Ra > Rb : La < Lb;
    });

    vector<int> points; int lastR = -1;
    for (int i = 0; i < N; i++) {
        int cur = sorted_points[i];
        int rcur = max(Row[cur], Col[cur]);
        if (rcur > lastR) {
            points.push_back(cur);
            lastR = rcur;
        }
    }

    n = points.size(); m = M; k = K;
    r.resize(n); c.resize(n); L.resize(n); R.resize(n);
    for (int i = 0; i < n; i++) {
        r[i] = Row[points[i]]; c[i] = Col[points[i]];

        L[i] = min(r[i], c[i]);
        R[i] = max(r[i], c[i]);
    }
}

struct Function {
    ll b, c;
    ll seg;

    Function(ll B = 0, ll C = INF, ll s = 0) : b(B), c(C), seg(s) {};

    ll evaluate(ll x) {
        return x*x + b*x + c;
    }
};

bool better(Function& f1, Function& f2, ll x) {
    ll v1 = f1.evaluate(x), v2 = f2.evaluate(x);
    if (v1 != v2) return v1 < v2;

    return f1.seg < f2.seg;
}

struct Node {
    Function best;
    Node *left, *right;

    Node() : best(Function()), left(nullptr), right(nullptr) {};
    Node(Function Best) : best(Best), left(nullptr), right(nullptr) {};
};

// implicit segtree storing minimum function at x for x in [0, 1m]
struct LiChaoTree {
    int lower, upper;
    Node* root;

    LiChaoTree() {};
    LiChaoTree(int L, int U) {
        lower = L;
        upper = U;

        root = new Node();
    }

    Node* update(Node* cur, int l, int r, Function fnew) {
        if (!cur) cur = new Node();
        
        int m = l + (r - l) / 2;
        if (better(fnew, cur->best, m)) swap(cur->best, fnew);

        if (better(fnew, cur->best, l)) cur->left = update(cur->left, l, m, fnew);
        else if (better(fnew, cur->best, r)) cur->right = update(cur->right, m, r, fnew);

        return cur;
    }

    pair<ll, ll> query(Node* cur, int l, int r, ll x) {
        if (!cur) return {INF, 0};
        pair<ll, ll> our_val = {cur->best.evaluate(x), cur->best.seg};
        if (l + 1 == r) return our_val;

        int m = l + (r - l) / 2;
        if (x < m) return min(our_val, query(cur->left, l, m, x));
        else return min(our_val, query(cur->right, m, r, x));
    }

    void update(Function fnew) {
        update(root, lower, upper+1, fnew);
    }

    pair<ll, ll> query(ll x) {
        return query(root, lower, upper+1, x);
    }
};


void compute_dp(ll lambda, vl& dp, vl &cnt, const vl &overlap) {
    dp.assign(n, INF);
    cnt.assign(n, 0);

    LiChaoTree lct(0, m+1);

    ll L0 = L[0] - 1;
    lct.update(Function(-2*L0, L0*L0 + lambda, 1));

    auto r0 = lct.query(R[0]);
    dp[0]  = r0.first;
    cnt[0] = r0.second;

    for (int i = 1; i < n; ++i) {
        ll Lj = L[i] - 1;
        ll B = -2 * Lj;
        ll C = dp[i-1] + Lj*Lj + lambda - overlap[i];

        int nseg = cnt[i-1] + 1;
        lct.update(Function(B, C, nseg));

        auto res = lct.query(R[i]);
        dp[i]  = res.first;
        cnt[i] = res.second;
    }
}

ll take_photos(int N, int M, int K, vi Row, vi Col) {
    preprocess(N, M, K, Row, Col);

    vl overlap(n, 0);
    for (int i = 1; i < n; i++) {
        ll over = max(0LL, R[i-1] - L[i] + 1);
        over *= over;

        overlap[i] = over;
    }

    ll lo = 0, hi = 1e13;           
    vector<ll> dp, cnt;

    while (lo < hi) {
        ll mid = (lo + hi) >> 1;
        compute_dp(mid, dp, cnt, overlap);
        if (cnt.back() > k) lo = mid + 1;   
        else hi = mid;    
    }

    compute_dp(lo, dp, cnt, overlap);
    return dp.back() - 1LL * lo * k;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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