Submission #1073055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073055		Mizo_Compiler	Aliens (IOI16_aliens)	C++17	25 / 100	28 ms	24156 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;
ll dp[N][2];
vector<int> R[M];

struct Line {
    mutable ll k, m, p;
    bool operator<(const Line &o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a, b) = a / b)
    // (for minimum, insert -k and -m and return -ans)
    static const ll inf = LLONG_MAX;
    ll div(ll a, ll b) {
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool isect(iterator x, iterator y) {
        if(y == end()) return x -> p = inf, 0;
        if(x -> k == y -> k) x -> p = x -> m > y -> m ? inf : -inf;
        else x -> p = div(y -> m - x -> m, x -> k - y -> k);
        return x -> p >= y -> p;
    }
    void add(ll k, ll m) {
        k = -k;
        m = -m;
        auto z = insert({k, m, 0}), y = z++, x = y;
        while(isect(y, z)) z = erase(z);
        if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while((y = x) != begin() && (--x) -> p >= y -> p) isect(x, erase(y));
    }
    int query(int x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return -(l.k * x + l.m);
    }
};

ll l[N], r[N];

long long take_photos(int n, int m, int k, std::vector<int> ro, std::vector<int> c) {
    vector<pair<int, int>> rng;
    for (int i = 0; i < n; i++) {
        int 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));
    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;
        LineContainer 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);
            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);
            dp[i][cur] = (r[i] * r[i]) + (2ll * r[i]) + 1ll + LC.query(r[i]);
            //cout << l[i] << " " << r[i] << " " << dp[i][cur] << " ez\n";
        }
    }
    return dp[n-1][cur];
}

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