Submission #500580

#	Time	Username	Problem	Language	Result	Execution time	Memory
500580		dooompy	Aliens (IOI16_aliens)	C++17	100 / 100	179 ms	11672 KiB

aliens

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

using namespace std;


template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

#define ll long long

struct line {
    ll m, c; int id;

    ll eval(ll x) {
        return m * x + c;
    }

    long double intersectX(line o) const {
        return (long double) (c - o.c) / (o.m - m);
    }
};

vector<pair<ll, ll>> points;

vector <line> cht ;
int cp;

void add ( line l) {
    auto n = cht.size();
    while (n >= 2 &&
           cht[n-1].intersectX(cht[n -2]) >= l.intersectX(cht[n-1])) {
        cht.pop_back();
        n = cht.size () ;
    }
    cht.push_back (l);
    cp = min (cp ,(int)cht.size() -1) ;
}
long long query ( long long x) {
    while (cp +1 != cht.size() &&
        cht [cp].intersectX(cht[cp +1]) < x) cp++;
    return cht [cp ].m*x + cht [cp].c;
}
pair<ll, ll> ct(ll c) {

    cht.clear();

    add({-2 * points[0].first, points[0].first * points[0].first - 2  * points[0].first, 0});

    int n= points.size();
    vector<ll> dp(n + 5);

    ll total = 0;

    for (int i = 0; i < n; i++) {
//        while (dq.size() >= 2 && dq[0].eval(points[i].second) >= dq[1].eval(points[i].second)) dq.pop_front();

        ll cur = query(points[i].second) + (points[i].second + 1) * (points[i].second + 1) + c;
        dp[i] = cur;
        total = cht[cp].id + 1;

        if (i == n-1) break;

        line l = {-2 * points[i+1].first, points[i + 1].first * points[i + 1].first - 2 * points[i + 1].first + dp[i] - max(points[i].second - points[i + 1].first + 1, 0LL) * max(points[i].second - points[i + 1].first + 1, 0LL), total};

//        while (dq.size() >= 2 && l.intersectX(dq.back()) <= dq.back().intersectX(dq[dq.size() - 2])) dq.pop_back();
//        dq.push_back(l);
        add(l);
    }

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

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {

    for (int i = 0; i < n; i++) {
        if (r[i] > c[i]) swap(r[i], c[i]);
        points.emplace_back(r[i], c[i]);
    }

    sort(points.begin(), points.end(), [](pair<int, int> a, pair<int, int> b) {
        if (a.second == b.second) {
            return a.first > b.first;
        } else return a.second < b.second;
    });

    vector<pair<ll, ll>> final;

    for (int i = 0; i < n; i++) {
        while (!final.empty() && final.back().first >= points[i].first) final.pop_back();
        final.push_back(points[i]);

    }

    points = final;

    test(points);

    ll left = 0, right = (ll) m * m;

    k = min(k, (int) points.size());

    while (left != right) {
        ll mid = (left + right) / 2;
        auto cur = ct(mid);
        if (cur.first > k) left = mid + 1;
        else right = mid;
    }

    auto ans = ct(left);

    return ans.second  - left * k;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int query(long long int)':
aliens.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     while (cp +1 != cht.size() &&
      |            ~~~~~~^~~~~~~~~~~~~
aliens.cpp: In function 'std::pair<long long int, long long int> ct(long long int)':
aliens.cpp:87:230: warning: narrowing conversion of 'total' from 'long long int' to 'int' [-Wnarrowing]
   87 |         line l = {-2 * points[i+1].first, points[i + 1].first * points[i + 1].first - 2 * points[i + 1].first + dp[i] - max(points[i].second - points[i + 1].first + 1, 0LL) * max(points[i].second - points[i + 1].first + 1, 0LL), total};
      |                                                                                                                                                                                                                                      ^~~~~

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