Submission #568262

#	Time	Username	Problem	Language	Result	Execution time	Memory
568262		ngpin04	Aliens (IOI16_aliens)	C++17	100 / 100	183 ms	9424 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}
const int N = 2e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <pair <int, long long>> seg;
vector <long double> inter;
vector <int> ind;

pair <int, int> a[N];

long long dp[N];

int ptr[N];
int cnt[N];
int n,m,k,sz,cur;

typedef long long ll;

long double intersect(pair <int, ll> a, pair <int, ll> b) {
    return (long double) (b.se - a.se) / (a.fi - b.fi);
}

bool good(pair <int, ll> a, pair <int, ll> b, pair <int, ll> c) {
    long double xM = intersect(a, c);
    long double xN = intersect(b, c);
    return xM < xN;
}

void addLine(pair <int, ll> s, int i) {
    while (sz > 1 && !good(seg[sz - 2], seg[sz - 1], s)) {
        seg.pop_back();
        inter.pop_back();
        ind.pop_back();
        sz--;
    }

    if (sz > 0)
        inter.push_back(intersect(s, seg.back()));
    seg.push_back(s);
    ind.push_back(i);
    sz++;
    mini(cur, sz - 2);
}

int getopt(int x) {
    while (cur + 1 < (int) inter.size() && x > inter[cur + 1])
        cur++;
    // cerr << x << " " << cur << "\n";
    return cur;
}

int solve(long long cost) {
    sz = 0;
    inter.clear();
    seg.clear();
    ind.clear();
    inter.push_back(-ooo);
    
    a[n + 1] = mp(oo, oo);
    for (int i = 1; i <= n; i++) {
        long long add = 1LL * (a[i].se + 1) * (a[i].se + 1);
        long long sub = 0;
        if (a[i].se >= a[i + 1].fi) {
            int d = a[i].se - a[i + 1].fi + 1;
            sub = 1LL * d * d;
        }

        long long y = (dp[i - 1] + 1LL * a[i].fi * a[i].fi) + cost;
        int x = -2 * a[i].fi;
        addLine(mp(x, y), i - 1);

        int it = -1;
        // long long res = ooo;
        // for (int j = 0; j < sz; j++) 
        //     if (mini(res, 1LL * seg[j].fi * (a[i].se + 1) 
        //     + seg[j].se - sub + add))
        //         it = j;

        it = getopt(a[i].se + 1);
        dp[i] = 1LL * seg[it].fi * (a[i].se + 1) + seg[it].se - sub + add;
        cnt[i] = cnt[ind[it]] + 1;
        ptr[i] = ind[it];
    }
    return cnt[n];
}

long long solve() {

    long long lo = -1;
    long long hi = 1e12 + 123;
    while (hi - lo > 1) {
        long long mid = (lo + hi) >> 1;
        if (solve(mid) > k)
            lo = mid;
        else
            hi = mid;
    }

    solve(hi);
    return dp[n] - k * hi;
}

void build() {
    for (int i = 1; i <= n; i++)
        if (a[i].fi > a[i].se)
            swap(a[i].fi, a[i].se);
    
    sort(a + 1, a + n + 1, [](pair <int, int> a, pair <int, int> b) {
        return (a.fi < b.fi) || (a.fi == b.fi && a.se > b.se);
    });

    int cur = -oo;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i].se > cur) {
            cur = a[i].se;
            a[++cnt] = a[i];
        }
    }
    n = cnt;
}

long long take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c) {
    n = _n;
    m = _m;
    k = _k;
    for (int i = 1; i <= n; i++)
        a[i] = mp(r[i - 1], c[i - 1]);
    build();
    return solve();
}

//#include "grader.cpp"

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