Submission #1076781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076781		asdasdqwer	Aliens (IOI16_aliens)	C++14	60 / 100	2041 ms	358772 KiB

aliens

#include "aliens.h"

#define ll long long
#define pii array<ll,2>
#define tii array<ll,3>

#include <bits/stdc++.h>
using namespace std;

struct Event {
    int pos;
    int other;
    bool isStart = true;
    int idx=0;
    bool operator<(const Event &x) {
        if (pos != x.pos) return pos < x.pos;
        if (idx != x.idx) return !isStart;
        return isStart;
    }
};

vector<pii> compress(vector<pii> x) {
    vector<pii> ret;
    for (auto y:x) {
        while (ret.size() && ret.back()[0] == y[0]) ret.pop_back();
        ret.push_back(y);
    }

    // now remove all with same ending positions
    for (auto &x:ret) swap(x[0], x[1]);
    sort(ret.begin(), ret.end());

    vector<pii> fr;
    for (auto &y:ret) {
        swap(y[0], y[1]);
        if (fr.size() && fr.back()[1] == y[1]) continue;
        fr.push_back(y);
    }

    sort(fr.begin(), fr.end());
    return fr;
}



void rec(int j, int l, int r, vector<vector<ll>> &dp, vector<pii> &intv, int optl, int optr) {
    if (l > r) return;
    int m = (l+r)/2;
    int opt = -1;
    dp[m][j] = dp[m][j-1];

    for (int k=optl;k<=min(optr, m);k++) {
        ll cur = (k > 0 ? dp[k-1][j-1] : 0);
        ll cost = (intv[m][1] - intv[k][0] + 1) * (intv[m][1] - intv[k][0] + 1);
        if (k > 0 && intv[k-1][1] >= intv[k][0]) {
            cost -= (intv[k-1][1] - intv[k][0] + 1) * (intv[k-1][1] - intv[k][0] + 1);
        }

        cur += cost;
        if (cur <= dp[m][j]) {
            opt = k;
            dp[m][j] = cur;
        }
    }

    rec(j, l, m-1, dp, intv, optl, opt);
    rec(j, m+1, r, dp, intv, opt, optr);
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    for (int i=0;i<n;i++) {
        if (r[i] < c[i])swap(r[i], c[i]);
    }

    vector<pii> intv(n);
    for (int i=0;i<n;i++) {
        intv[i]={c[i], r[i]};
    }

    sort(intv.begin(), intv.end());
    intv.erase(unique(intv.begin(), intv.end()), intv.end());

    intv = compress(intv);

    vector<Event> vv;
    int tmp=0;
    for (auto &x:intv) {
        Event e1;e1.pos=x[0];e1.other=x[1];e1.idx=tmp++;
        vv.push_back(e1);
        swap(e1.pos, e1.other);e1.isStart=false;
        vv.push_back(e1);
    }

    sort(vv.begin(), vv.end());
    multiset<int> starts;
    vector<bool> ers(intv.size(), false);
    for (auto &x:vv) {
        if (x.isStart) {
            starts.insert(x.pos);
        }

        else {
            starts.erase(starts.find(x.other));
            if (starts.size()) {
                int mn = *starts.begin();
                if (mn < x.other) ers[x.idx]=true;
            }
        }
    }

    vector<pii> newInvs;
    for (int i=0;i<(int)intv.size();i++) {
        if (ers[i]) continue;
        newInvs.push_back(intv[i]);
    }

    intv = newInvs;

    n = (int)intv.size();
    k = min(k, n);
    vector<vector<ll>> dp(n, vector<ll>(k, 1e18));

    for (int i=0;i<n;i++) {
        dp[i][0] = (intv[i][1] - intv[0][0] + 1) * (intv[i][1] - intv[0][0] + 1);
    }

    for (int j=1;j<k;j++) {
        rec(j, 0, n-1, dp, intv, 0, n);
    }

    // for (auto &x:dp) {
    //     for (ll y:x) {
    //         cout << y << " ";
    //     }
    //     cout << "\n";
    // }

    return dp[n-1][k-1];
}

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