Submission #1073234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073234		Mizo_Compiler	Aliens (IOI16_aliens)	C++17	100 / 100	137 ms	37104 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
#define F first
#define S second
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define pb push_back
const int N = 1e5+5, M = 1e6+1;
pair<ll, int> dp[N];
//ll dp[N][2];
vector<int> R[M];
 
struct Line {
    long long m, c;
    int cnt;
    Line() {}
    Line(long long _m, long long _c, int _cnt) : m(_m), c(_c), cnt(_cnt) {}
    long long eval(long long x) const { return m * x + c; }
};
 
struct CHT {
    deque <Line> lines;
    bool is_invalid(const Line &l1, const Line &l2, const Line &l3) {
        return (l3.c - l1.c) * (l1.m - l2.m) <= (l2.c - l1.c) * (l1.m - l3.m);
    }
    void add(ll m, ll c, int ctr) {
        Line new_line(m, c, ctr);
        while(sz(lines) >= 2 && is_invalid(lines[sz(lines) - 2], lines.back(), new_line)) lines.pop_back();
        lines.push_back(new_line);
    }
    pair<ll, int> query(long long x) {
        while(sz(lines) >= 2 && lines[0].eval(x) > lines[1].eval(x)) lines.pop_front();
        return {lines[0].eval(x), lines[0].cnt + 1};
    }
};
 
ll l[N], r[N];
 
long long take_photos(int n, int m, int k, std::vector<int> roo, std::vector<int> co) {
    vector<ll> ro, c;
    for (auto &i : roo)ro.push_back(i);
    for (auto &i : co)c.push_back(i);
    vector<pair<ll, ll>> rng;
    for (int i = 0; i < n; i++) {
        ll l = min(ro[i], c[i]), rr = max(ro[i], c[i]);
        R[rr].push_back(l);
    }
    int mnl = 1e9;
    for (int i = m; i >= 0; i--) {
        sort(all(R[i]));
        for (auto &l : R[i]) {
            if (mnl > l)rng.push_back({l, i});
            mnl = min(mnl, l);
        }
        R[i].clear();
    }
    sort(all(rng));
    n = sz(rng);
    k = min(k, sz(rng));
    ll st = 0, ed = ll(m) * ll(m), ans = 1e18;
    for (int i = 0; i < n; i++) {
        l[i] = rng[i].F;
        r[i] = rng[i].S;
    }
    while (st <= ed) {
        ll md = (st + ed) / 2ll;
        CHT ch;
        for (int i = 0; i < n; i++) {
            ll cc = 0;
            if (i) {
                ll xx = max(0ll, r[i-1]-l[i]+1);
                cc = dp[i-1].F - (xx * xx);
            }
            //cout << "bad: " << 2ll * l[i] << " " << -2ll * l[i] + (l[i] * l[i]) + cc << "\n";
            ch.add(-2ll * l[i], -2ll * l[i] + (l[i] * l[i]) + cc, (i == 0 ? 0 : dp[i-1].S));
            pair<ll, int> xx = ch.query(r[i]);
            dp[i] = {md + (r[i] * r[i]) + (2ll * r[i]) + 1ll + xx.F, xx.S};
            //cout << l[i] << " " << r[i] << " " << md << " " << dp[i].F << " " << dp[i].S << " ez2\n";
        }
        if (dp[n-1].S <= k) {
            ans = dp[n-1].F - md * ll(k);
            ed = md - 1;
        } else {
            st = md + 1;
        }
    }
    /*int cur = 0, prv = 1;
    for (int i = 0; i < n; i++) {
        l[i] = rng[i].F, r[i] = rng[i].S;
        dp[i][cur] = (r[i] - l[0] + 1ll) * (r[i] - l[0] + 1ll);
        //cout << l[i] << " " << r[i] << " " << dp[i][cur] << " ez\n";
    }
    for (int ii = 0; ii+1 < k; ii++) {
        cur ^= 1;
        prv ^= 1;
        CHT LC;
        for (int i = 0; i <= ii; i++) {
            ll cc = 0;
            if (i) {
                ll xx = max(0ll, r[i-1]-l[i]+1);
                cc = dp[i-1][prv] - (xx * xx);
            }
            LC.add(-2ll * l[i], -2ll * l[i] + (l[i] * l[i]) + cc, 0);
            dp[i][cur] = dp[i][prv];
            //cout << l[i] << " " << r[i] << " " << dp[i][cur] << " ez\n";
        }
        for (int i = ii+1; i < n; i++) {
            ll cc = 0;
            if (i) {
                ll xx = max(0ll, r[i-1]-l[i]+1);
                cc = dp[i-1][prv] - (xx * xx);
            }
            LC.add(-2ll * l[i], -2ll * l[i] + (l[i] * l[i]) + cc, 0);
            dp[i][cur] = (r[i] * r[i]) + (2ll * r[i]) + 1ll + LC.query(r[i]).F;
            //cout << l[i] << " " << r[i] << " " << dp[i][cur] << " ez\n";
        }
    }
    ans = dp[n-1][cur];*/
    return ans;
}

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