Submission #1102526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102526		Zero_OP	Aliens (IOI16_aliens)	C++14	100 / 100	170 ms	8896 KiB

aliens

#include <bits/stdc++.h>
#ifndef LOCAL
    #include "aliens.h"
#endif // LOCAL

using namespace std;
using ll = long long;

#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v)
#define dbg(x) "[" #x " = " << (x) << "]"
#define sz(v) (int)v.size()

template<typename T> bool minimize(T& a, const T& b){
    if(a > b) return a = b, true; return false;
}

template<typename T> bool maximize(T& a, const T& b){
    if(a < b) return a = b, true; return false;
}

const ll inf = 1e18;

struct line{
    ll a, b, cnt, p;
    line(ll a = 0, ll b = 0, ll cnt = 0, ll p = 0) : a(a), b(b), cnt(cnt), p(p) {}
    ll eval(ll x){ return a * x + b; }
};

ll divi(ll a, ll b){
    return a / b - ((a ^ b) < 0 && (a % b) != 0);
}

void isect(line& d1, line& d2){
    if(d1.a == d2.a) d1.p = (d1.b > d2.b ? inf : -inf);
    else d1.p = divi(d2.b - d1.b, d1.a - d2.a);
}

struct ConvexHullTrick{
    deque<line> v;

    ConvexHullTrick() : v() {}

    void init(){
        deque<line>().swap(v);
    }

    void add(line d){
        d.p = inf;
        if(!v.empty()) isect(v.back(), d);

        while((int)v.size() > 1 && v[(int)v.size() - 2].p >= v.back().p){
            v.pop_back();
            isect(v.back(), d);
        }

        v.push_back(d);
    }

    pair<ll, int> query(ll x){
        while((int)v.size() > 1){
            ll l = v[0].eval(x);
            ll r = v[1].eval(x);
            if(l != r){
                if(l > r) v.pop_front();
                if(l < r) break;
            } else{
                if(v[0].cnt > v[1].cnt) v.pop_front();
                else break;
            }
        }

        return {v[0].eval(x), v[0].cnt};
    }

} cht;

ll square(ll x){
    return x * x;
}

long long take_photos(int n, int m, int k, std::vector<int> l, std::vector<int> r) {
    vector<int> diagonal(n);
    for(int i = 0; i < n; ++i){
        if(l[i] > r[i]) swap(l[i], r[i]);
    }

    vector<int> pos(n);
    iota(all(pos), 0);
    sort(all(pos), [&](int i, int j){
        if(l[i] != l[j]) return l[i] < l[j];
        return r[i] > r[j];
    });

    int ptr = 0;
    vector<pair<int, int>> after;
    for(int i : pos){
        int x = l[i], y = r[i];
        if(!after.empty() && after.back().second >= y) continue;
        after.push_back({x, y});
    }

    n = sz(after);
    vector<ll> L(n), R(n);
    for(int i = 0; i < n; ++i){
        tie(L[i], R[i]) = after[i];
        assert(i == 0 || (L[i - 1] <= L[i] && R[i - 1] <= R[i]));
        --L[i]; //for (R[j] - L[i])^2 instead of (R[j] - L[i] + 1)^2
    }

    auto cost = [&](int i, int j){
        --i, --j;
        ll ret = square(R[j] - L[i]);
        if(i > 0) ret -= square(max(0ll, R[i - 1] - L[i]));
        return ret;
    };

    vector<ll> dp(n + 1);
    vector<int> cnt(n + 1);
    auto f = [&](ll lambda) -> pair<ll, int>{
        cht.init();
        for(int i = 0; i < n; ++i){
            ll extra = square(max(0ll, i > 0 ? R[i - 1] - L[i] : 0));
            cht.add(line(-2 * L[i], dp[i] + L[i] * L[i] - extra, cnt[i]));
            pair<ll, int> q = cht.query(R[i]);
            dp[i + 1] = q.first + lambda + R[i] * R[i];
            cnt[i + 1] = q.second + 1;
        }
        return {dp[n], cnt[n]};
    };

    ll lo = 0, hi = +1e18, ans = 0;
    while(lo <= hi){
        ll mid = lo + hi >> 1;
        pair<ll, int> eval = f(mid);
        if(eval.second <= k){
            ans = mid;
            hi = mid - 1;
        } else lo = mid + 1;
    }

    pair<ll, int> ret = f(ans);
    ll last = ret.first - k * ans;
    return last;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> r(n), c(n);
    for(int i = 0; i < n; ++i) cin >> r[i] >> c[i];

    cout << take_photos(n, m, k, r, c) << '\n';

    return 0;
}
#endif //LOCAL

Compilation message (stderr)

aliens.cpp: In function 'bool minimize(T&, const T&)':
aliens.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |     if(a > b) return a = b, true; return false;
      |     ^~
aliens.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
aliens.cpp: In function 'bool maximize(T&, const T&)':
aliens.cpp:19:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   19 |     if(a < b) return a = b, true; return false;
      |     ^~
aliens.cpp:19:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   19 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:134:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  134 |         ll mid = lo + hi >> 1;
      |                  ~~~^~~~
aliens.cpp:95:9: warning: unused variable 'ptr' [-Wunused-variable]
   95 |     int ptr = 0;
      |         ^~~
aliens.cpp:111:10: warning: variable 'cost' set but not used [-Wunused-but-set-variable]
  111 |     auto cost = [&](int i, int j){
      |          ^~~~

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