Submission #1122835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122835		dbence	Aliens (IOI16_aliens)	C++20	60 / 100	2096 ms	51016 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 (r <= l + 1) {
            return max(calc(l), calc(r));
        }
        ll q = l + r >> 1;
        if (calc(q) > calc(q + 1)) {
            return ternary_search(l, q);
        } else {
            return ternary_search(q + 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.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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