Submission #1301489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301489		ProtonDecay314	Aliens (IOI16_aliens)	C++17	60 / 100	2097 ms	51036 KiB

aliens

#pragma GCC optimize ("Ofast,__attribute__((always_inline))")
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;

#define INF(dt) numeric_limits<dt>::max()
#define fi first
#define se second

// Create a struct for linear functions
// First argument: slope, second argument: y-intercept
struct Line {
    int m;

    ll b;

    int b2;

    inline pair<ll, int> evaluate(ll x) const {
        return {m * x + b, b2};
    }
};

/*
Maintain the minimum line in the li chao tree
*/
class Tree {
    public:
        Tree *lt, *rt;
        int l, r;
        Line v;

        Tree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v({0, INF(ll), INF(int)}) {}

        void build() {
            if(l == r || (lt != nullptr)) {
                return;
            }

            int m = (l + r) >> 1;

            lt = new Tree(l, m);
            rt = new Tree(m + 1, r);
        }

        void insert_line(Line nl) {
            build();
            int m = (l + r) >> 1;
            bool less_l = nl.evaluate(l) < v.evaluate(l);
            bool less_m = nl.evaluate(m + 1) < v.evaluate(m + 1);

            /*
            ! TODO why does swap work
            ! and v = nl does not???

            well, if we do v = nl,
            we simply erase v from existence
            we don't want that---we want to consider both

            so nl is considered now
            therefore we instead propagate v downward
            */
            if(less_m) swap(v, nl);

            if(l != r) {
                (less_l == less_m ? rt: lt)->insert_line(nl);
            }
        }

        pair<ll, int> evaluate(int x) {
            build();
            if(l == r) {
                return v.evaluate(x);
            }
            return min((x <= ((l + r) >> 1) ? lt : rt)->evaluate(x), v.evaluate(x));
        }

        ~Tree() {
            if(lt != nullptr) {
                delete lt;
                delete rt;
            }
        }
};

/*
Suppose the penalty for using another picture is +y
*/
pll solve_lambda_brute(const vpll& pts, ll m, ll y) {
    ll np = pts.size();
    
    // note: stores NEGATIVE area, num pictures
    // then, the DP just gets the maximum state
    vector<pair<ll, int>> dp(np, {0ll, 0});

    Tree * tr = new Tree(0ll, m - 1ll);
    tr->build();

    for(ll i = 0ll; i < np; i++) {
        ll cl = pts[i].fi, cr = pts[i].se;

        if(i == 0ll) {
            tr->insert_line({- ((int)(pts[i].fi) << 1), y + pts[i].fi * pts[i].fi, -1});
        } else {
            ll overlap = max(pts[i - 1ll].se - pts[i].fi + 1ll, 0ll);
            tr->insert_line({- ((int)(pts[i].fi) << 1), dp[i - 1ll].fi - overlap * overlap + y + pts[i].fi * pts[i].fi, dp[i - 1ll].se - 1});
        }

        pair<ll, int> opt = tr->evaluate(cr + 1ll);

        dp[i] = {opt.fi + (cr + 1ll) * (cr + 1ll), opt.se};

        // cerr << y << " " << i << " " << dp[i].fi << " " << -dp[i].se << endl;
    }

    delete tr;

    return dp[np - 1ll];
}

ll take_photos(int i_n, int i_m, int i_k, vi r, vi c) {
    ll n = i_n, m = i_m, k = i_k;

    // first, we preprocess. remove all redundant points

    vpll pts;

    for(ll i = 0ll; i < n; i++) {
        if(r[i] > c[i]) swap(r[i], c[i]);

        pts.push_back({r[i], c[i]});
    }

    sort(pts.begin(), pts.end(), [](pll p1, pll p2){return p1.fi < p2.fi || (p1.fi == p2.fi && p1.se > p2.se);});

    ll max_r = -1ll;

    vpll filt_pts;

    for(ll i = 0ll; i < n; i++) {
        ll cl = pts[i].fi, cr = pts[i].se;

        if(cr > max_r) {
            filt_pts.push_back(pts[i]);
            // cerr << cl << " " << cr << endl;
            max_r = cr;
        }
    }

    // Performing lagrangian relaxation
    ll lo = 0ll, hi = 1e11;

    while(hi - lo > 1ll) {
        ll mid = (lo + hi) >> 1ll;

        pll cpair = solve_lambda_brute(filt_pts, m, mid);

        ll c_k = -cpair.se;

        if(c_k >= k) lo = mid;
        else hi = mid;
    }

    return solve_lambda_brute(filt_pts, m, lo).fi - k * lo;
}

Compilation message (stderr)

aliens.cpp:1:61: warning: bad option '-f__attribute__((always_inline))' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize ("Ofast,__attribute__((always_inline))")
      |                                                             ^
In file included from aliens.cpp:2:
aliens.h:5:82: warning: bad option '-f__attribute__((always_inline))' to attribute 'optimize' [-Wattributes]
    5 | long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c);
      |                                                                                  ^
aliens.h:5:82: warning: bad option '-f__attribute__((always_inline))' to attribute 'optimize' [-Wattributes]
aliens.cpp:28:41: warning: bad option '-f__attribute__((always_inline))' to attribute 'optimize' [-Wattributes]
   28 |     inline pair<ll, int> evaluate(ll x) const {
      |                                         ^~~~~
aliens.cpp:42:30: warning: bad option '-f__attribute__((always_inline))' to attribute 'optimize' [-Wattributes]
   42 |         Tree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v({0, INF(ll), INF(int)}) {}
      |                              ^
aliens.cpp:44:20: warning: bad option '-f__attribute__((always_inline))' to attribute 'optimize' [-Wattributes]
   44 |         void build() {
      |                    ^
aliens.cpp:55:33: warning: bad option '-f__attribute__((always_inline))' to attribute 'optimize' [-Wattributes]
   55 |         void insert_line(Line nl) {
      |                                 ^
aliens.cpp:79:37: warning: bad option '-f__attribute__((always_inline))' to attribute 'optimize' [-Wattributes]
   79 |         pair<ll, int> evaluate(int x) {
      |                                     ^
aliens.cpp:87:15: warning: bad option '-f__attribute__((always_inline))' to attribute 'optimize' [-Wattributes]
   87 |         ~Tree() {
      |               ^
aliens.cpp:98:51: warning: bad option '-f__attribute__((always_inline))' to attribute 'optimize' [-Wattributes]
   98 | pll solve_lambda_brute(const vpll& pts, ll m, ll y) {
      |                                                   ^
aliens.cpp:130:53: warning: bad option '-f__attribute__((always_inline))' to attribute 'optimize' [-Wattributes]
  130 | ll take_photos(int i_n, int i_m, int i_k, vi r, vi c) {
      |                                                     ^
aliens.cpp: In function 'll take_photos(int, int, int, vi, vi)':
aliens.cpp:143:51: warning: bad option '-f__attribute__((always_inline))' to attribute 'optimize' [-Wattributes]
  143 |     sort(pts.begin(), pts.end(), [](pll p1, pll p2){return p1.fi < p2.fi || (p1.fi == p2.fi && p1.se > p2.se);});
      |                                                   ^
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