Submission #500498

#	Time	Username	Problem	Language	Result	Execution time	Memory
500498		dooompy	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 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;

pair<ll, ll> ct(ll c) {
    deque<line> dq;

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

    int n= points.size();
    vector<int> ct(n + 5);
    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 = dq.front().eval(points[i].second) + (points[i].second + 1) * (points[i].second + 1) + c;
        dp[i] = cur;
        total = dq.front().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, 0) * max(points[i].second - points[i + 1].first + 1, 0), total};

        while (dq.size() >= 2 && l.intersectX(dq.back()) <= dq.back().intersectX(dq[dq.size() - 2])) dq.pop_back();
        dq.push_back(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 'std::pair<long long int, long long int> ct(long long int)':
aliens.cpp:69:170: error: no matching function for call to 'max(long long int, int)'
   69 |         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, 0) * max(points[i].second - points[i + 1].first + 1, 0), total};
      |                                                                                                                                                                          ^
In file included from /usr/include/c++/10/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
aliens.cpp:69:170: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   69 |         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, 0) * max(points[i].second - points[i + 1].first + 1, 0), total};
      |                                                                                                                                                                          ^
In file included from /usr/include/c++/10/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
aliens.cpp:69:170: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   69 |         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, 0) * max(points[i].second - points[i + 1].first + 1, 0), total};
      |                                                                                                                                                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
aliens.cpp:69:170: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   69 |         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, 0) * max(points[i].second - points[i + 1].first + 1, 0), total};
      |                                                                                                                                                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
aliens.cpp:69:170: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   69 |         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, 0) * max(points[i].second - points[i + 1].first + 1, 0), total};
      |                                                                                                                                                                          ^
aliens.cpp:69:223: error: no matching function for call to 'max(long long int, int)'
   69 |         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, 0) * max(points[i].second - points[i + 1].first + 1, 0), total};
      |                                                                                                                                                                                                                               ^
In file included from /usr/include/c++/10/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
aliens.cpp:69:223: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   69 |         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, 0) * max(points[i].second - points[i + 1].first + 1, 0), total};
      |                                                                                                                                                                                                                               ^
In file included from /usr/include/c++/10/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
aliens.cpp:69:223: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   69 |         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, 0) * max(points[i].second - points[i + 1].first + 1, 0), total};
      |                                                                                                                                                                                                                               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
aliens.cpp:69:223: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   69 |         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, 0) * max(points[i].second - points[i + 1].first + 1, 0), total};
      |                                                                                                                                                                                                                               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from aliens.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
aliens.cpp:69:223: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   69 |         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, 0) * max(points[i].second - points[i + 1].first + 1, 0), total};
      |                                                                                                                                                                                                                               ^