Submission #1102366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102366		Zero_OP	Aliens (IOI16_aliens)	C++14	12 / 100	2 ms	444 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];
        after.push_back({x, y});
        while(sz(after) > 1){
            if(after[sz(after) - 2].first <= after.back().first && after[sz(after) - 2].second >= after.back().second){
                after.pop_back();
            } else break;
        }
    }

    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
    }

    vector<ll> dp(n);
    vector<int> cnt(n);

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

        return {dp[n - 1], cnt[n - 1]};
    };

    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);

    cout << take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}) << '\n';
    cout << take_photos(2, 6, 2, {1, 4}, {4, 1}) << '\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:132:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |         ll mid = lo + hi >> 1;
      |                  ~~~^~~~
aliens.cpp:95:9: warning: unused variable 'ptr' [-Wunused-variable]
   95 |     int ptr = 0;
      |         ^~~

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