Submission #1119770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119770		dbence	Aliens (IOI16_aliens)	C++14	41 / 100	2016 ms	26616 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;
     
    int n, m, k, lef[M], xs[N];
     
    ll ans[M];
     
    struct Node {
        int l, r;
        int a;
        ll b;
    } node[N << 2];
     
    struct Change {
        int id;
        int a;
        ll b;
    };
    vector <Change> changes[N];
     
    ll eval(ll a, ll b, int x) {
        return 1ll * a * xs[x] + b;
    }
     
    void update(int id, int a, ll b, vector <Change> &changes) {
        int q = node[id].l + node[id].r >> 1;
        int 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(int id, ll x) {
        ll f = eval(node[id].a, node[id].b, x);
        if (node[id].l == node[id].r) {
            return f;
        }
        int 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(int 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;
        }
        int 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 (int 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) {
            int i = xs[j];
            if (j && i == xs[j - 1]) {
                continue;
            }
            while (!st.empty() && st.top().yy > lef[i]) {
                rollback(st.top().xx);
                st.pop();
            }
            int p = st.empty()? 0: xs[st.top().xx];
            int l = lef[i];
            
            update(0, -2 * (l - 1), 1ll * (l - 1) * (l - 1) + ans[p] - 1ll * max(0, p - l + 1) * max(0, p - l + 1), changes[j]);
            st.push({j, lef[i]});
     
            res = ans[i] = lambda + 1ll * 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 (int i = 1; i <= m; ++i) {
            lef[i] = i + 1;
        }
        for (int i = 0; i < n; ++i) {
            r[i]++, c[i]++;
            int x = max(r[i], c[i]);
            int 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(int, int, ll, std::vector<Change>&)':
aliens.cpp:39:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int q = node[id].l + node[id].r >> 1;
      |                 ~~~~~~~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'll query(int, ll)':
aliens.cpp:61:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         int q = node[id].l + node[id].r >> 1;
      |                 ~~~~~~~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'void build(int, ll, ll)':
aliens.cpp:77:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         int q = node[id].l + node[id].r >> 1;
      |                 ~~~~~~~~~~~^~~~~~~~~~~~
aliens.cpp: In lambda function:
aliens.cpp:91:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |             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: 0 / 19
• Subtask 6: 0 / 40