Submission #384728

#	Time	Username	Problem	Language	Result	Execution time	Memory
384728		anachor	Aliens (IOI16_aliens)	C++17	100 / 100	232 ms	8420 KiB

aliens

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+7;
typedef long long LL;
typedef pair<LL, LL> PLL;

long long sq(long long z)   {return z*z;}
PLL operator+(PLL a, PLL b) {
    return PLL(a.first+b.first, a.second+b.second);
}

struct CHT {
    vector<LL> M, C, P;
    int ptr = 0;

    CHT(int n) {
        M.reserve(n+1);
        C.reserve(n+1);
        P.reserve(n+1);
    }

    ///Use double comp if M,C is LL range
    bool useless(int l1, int l2, int l3) {
        return (C[l3]-C[l1])*(M[l1]-M[l2]) < (C[l2]-C[l1])*(M[l1]-M[l3]);
    }

    PLL f(int id, LL x) {
        return {M[id]*x+C[id], P[id]+1};
    }

    void add(LL m, LL c, LL p) {
        M.push_back(m);
        C.push_back(c);
        P.push_back(p);
        int s = M.size();

        while (s >= 3 && useless(s-3, s-2, s-1)) {
            M.erase(M.end()-2);
            C.erase(C.end()-2);
            P.erase(P.end()-2);
            s--;
        }
    }

    PLL query(LL x) {
        if (ptr >= M.size()) ptr = M.size()-1;
        while (ptr < M.size()-1 && f(ptr, x) >= f(ptr+1, x)) ptr++; /// change > to < for maximum
        return f(ptr, x);
    }
};
int x[N], y[N];
PLL dp[N];
PLL check(long long c, int n, int *x, int *y) {
    CHT cht(n);
    for (int i=1; i<=n; i++) {
        LL C = dp[i-1].first + sq(x[i]) - sq(max(0, y[i-1]-x[i]));
        LL M = -2*x[i];
        cht.add(M, C, dp[i-1].second);
        dp[i] = cht.query(y[i]);
        dp[i].first += sq(y[i]) + c;
    }
    return dp[n];
}

long long take_photos(int n, int N, int k, vector<int> xx, vector<int> yy) {
    vector<pair<int, int>> ranges;
    for (int i=0; i<n; i++) {
        ranges.push_back({max(xx[i], yy[i]), -min(xx[i], yy[i])});
    }
    sort(ranges.begin(), ranges.end());

    vector<pair<int, int>> r2;
    for (auto pr: ranges) {
        int r = pr.first, l = -pr.second;
        while (r2.size() && r2.back().first >= l)   r2.pop_back();
        r2.push_back({l, r});
    }

    n = r2.size();
    k = min(k, n);
    for (int i=1; i<=n; i++) {
        x[i] = r2[i-1].first, y[i] = r2[i-1].second+1;
    }
    long long lo = -1e12, hi = 1e12;
    while (lo < hi) {
        long long mid = lo + (hi-lo)/2;
        if (check(mid, n, x, y).second > k)      lo = mid+1;
        else                                     hi = mid;
    }
    return check(lo, n, x, y).first - k*lo;
}

Compilation message (stderr)

aliens.cpp: In member function 'PLL CHT::query(LL)':
aliens.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if (ptr >= M.size()) ptr = M.size()-1;
      |             ~~~~^~~~~~~~~~~
aliens.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         while (ptr < M.size()-1 && f(ptr, x) >= f(ptr+1, x)) ptr++; /// change > to < for maximum
      |                ~~~~^~~~~~~~~~~~

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