Submission #1024306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024306		dbence	Aliens (IOI16_aliens)	C++14	60 / 100	2029 ms	54644 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define xx first
#define yy second
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
using namespace std;

typedef long long ll;
const ll N = 1e5 + 1;
const ll M = 1e6 + 1;
const ll inf = 1ll << 60;

ll n, m, k, lef[M], xs[N], ans[M];

struct Node {
    ll l, r;
    ll a, b;
} node[M << 2];

struct Change {
    ll id;
    ll a, b;
};
vector <Change> changes[N];

ll eval(ll a, ll b, ll x) {
    return 1ll * a * xs[x] + b;
}

void update(ll id, ll a, ll b, vector <Change> &changes) {
    ll q = node[id].l + node[id].r >> 1;
    ll l = node[id].l;
    if (eval(node[id].a, node[id].b, q) > eval(a, b, q)) {
        swap(node[id].a, a);
        swap(node[id].b, b);
        changes.push_back({id, a, b});
    }
    if (node[id].l == node[id].r) {
        return;
    }
    if (eval(node[id].a, node[id].b, l) > eval(a, b, l)) {
        update(l(id), a, b, changes);
    } else {
        update(r(id), a, b, changes);
    }
}

ll query(ll id, ll x) {
    ll f = eval(node[id].a, node[id].b, x);
    if (node[id].l == node[id].r) {
        return f;
    }
    ll q = node[id].l + node[id].r >> 1;
    if (x <= q) {
        return min(f, query(l(id), x));
    } else {
        return min(f, query(r(id), x));
    }
}

void build(ll id, ll l, ll r) {
    node[id].l = l;
    node[id].r = r;
    node[id].a = 0;
    node[id].b = inf;
    if (l == r) {
        return;
    }
    ll q = node[id].l + node[id].r >> 1;
    build(l(id), l, q);
    build(r(id), q + 1, r);
}

ll calc(ll lambda) {
    stack <pair <ll, ll>> st;
    for (ll i = 0; i < n; ++i) {
        changes[i].clear();
    }
    fill(ans, ans + M, 0);
    build(0, 0, n - 1);

    auto rollback = [&](ll i) {
        for (auto [id, a, b]: changes[i]) {
            node[id].a = a;
            node[id].b = b;
        }
    };
    ll res = 0;
    for (int j = 0; j < n; ++j) {
        ll i = xs[j];
        if (j && i == xs[j - 1]) {
            continue;
        }
        while (!st.empty() && st.top().yy > lef[i]) {
            rollback(st.top().xx);
            st.pop();
        }
        ll p = st.empty()? 0: xs[st.top().xx];
        ll l = lef[i];
        
        update(0, -2 * (l - 1), (l - 1) * (l - 1) + ans[p] - max(0ll, p - l + 1) * max(0ll, p - l + 1), changes[j]);
        st.push({j, lef[i]});

        res = ans[i] = lambda + i * i + query(0, j);
    }
    return res - k * lambda;
}

ll ternary_search(ll l, ll r) {
    if (l == r) {
        return calc(l);
    }
    ll d = (r - l) / 3;
    ll a = l + d;
    ll b = r - d;
    if (calc(a) > calc(b)) {
        return ternary_search(l, b - 1);
    } else {
        return ternary_search(a + 1, r);
    }
}

ll take_photos(int n_, int m_, int k_, std::vector<int> r, std::vector<int> c) {
    n = n_, m = m_, k = k_;
    for (ll i = 1; i <= m; ++i) {
        lef[i] = i + 1;
    }
    for (ll i = 0; i < n; ++i) {
        r[i]++, c[i]++;
        ll x = max(r[i], c[i]);
        ll y = min(r[i], c[i]);

        lef[x] = min(lef[x], y);
        xs[i] = x;
    }
    sort(xs, xs + n);
    ll res = ternary_search(0, 1ll * m * m);
    return res;
}

Compilation message (stderr)

aliens.cpp: In function 'void update(ll, ll, ll, std::vector<Change>&)':
aliens.cpp:35:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     ll q = node[id].l + node[id].r >> 1;
      |            ~~~~~~~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'll query(ll, ll)':
aliens.cpp:57:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     ll q = node[id].l + node[id].r >> 1;
      |            ~~~~~~~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'void build(ll, ll, ll)':
aliens.cpp:73:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     ll q = node[id].l + node[id].r >> 1;
      |            ~~~~~~~~~~~^~~~~~~~~~~~
aliens.cpp: In lambda function:
aliens.cpp:87:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |         for (auto [id, a, b]: changes[i]) {
      |                   ^

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