Submission #1140209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140209		gyg	Aliens (IOI16_aliens)	C++20	0 / 100	40 ms	63048 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second 
const int N = 4e3 + 5, K = 4e3 + 5, M = 1e6 + 5, INF = 1e18;

int n, k;
arr<int, N> lf, rg, mx;

// Make lazy create
struct Lch {
    int evl(pii x, int y) { return x.fir * y + x.sec; }
    arr<pii, 4 * M> ln;

    void intl() { ln.fill({0, INF}); }
    void ins(pii x, int u = 1, int lw = 0, int hg = M) {
        int md = (lw + hg) / 2;
        if (evl(x, md) < evl(ln[u], md)) swap(x, ln[u]);
        if (lw == hg) return;
        if (evl(x, lw) < evl(ln[u], lw)) ins(x, 2 * u, lw, md);
        else ins(x, 2 * u + 1, md + 1, hg);
    }
    int qry(int x, int u = 1, int lw = 0, int hg = M) {
        if (lw == hg) return evl(ln[u], x);
        int md = (lw + hg) / 2;
        if (x <= md) return min(evl(ln[u], x), qry(x, 2 * u, lw, md));
        return min(evl(ln[u], x), qry(x, 2 * u + 1, md + 1, hg));
    }
} lch;

arr<arr<int, K>, N> dp;
int sq(int x) { return x * x; }
void dp_cmp() {
    lch.intl();
    for (int i = 1; i <= n; i++) 
        dp[i][1] = sq(rg[i] - lf[1] + 1);

    for (int c = 2; c <= k; c++) {
        lch.intl();
        for (int i = 1; i <= n; i++) {
            dp[i][c] = sq(rg[i]) + 2 * rg[i] + 1 + lch.qry(rg[i]);
            lch.ins({-2 * mx[i], sq(mx[i]) - 2 * mx[i] + dp[i][c - 1]});
        }
    }

    // for (int i = 1; i <= n; i++)
    //     for (int c = 1; c <= k; c++) 
    //         cout << i << " " << c << ": " << dp[i][c] << endl;
}

map<int, int> rng;
int take_photos(signed _sz, signed _m, signed _k, vec<signed> _rw, vec<signed> _cl) {
    k = _k;
    for (int i = 0; i < _sz; i++)
        rng[min(_rw[i], _cl[i])] = max(rng[min(_rw[i], _cl[i])], (int) max(_rw[i], _cl[i]));
    int mx_rg = 0;
    vec<int> dlt;
    for (pii x : rng) {
        if (x.sec <= mx_rg) dlt.push_back(x.fir);
        else mx_rg = x.sec;
    }
    for (int x : dlt) rng.erase(x);
    while (rng.size()) {
        pii x = *rng.begin(); rng.erase(rng.begin());
        n++, lf[n] = x.fir, rg[n] = x.sec;
    }
    for (int i = 1; i <= n; i++) mx[i] = max(rg[i], lf[i + 1]);

    // cout << n << endl;
    // for (int i = 1; i <= n; i++) cout << lf[i] << " " << rg[i] << endl;

    dp_cmp();

    int ans = *min_element(dp[n].begin() + 1, dp[n].begin() + k + 1);
    return ans;
}

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: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40