Submission #821717

#	Time	Username	Problem	Language	Result	Execution time	Memory
821717		rembocoder	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 KiB

aliens

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

using namespace std;

bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
    if (a.first != b.first) {
        return a.first < b.first;
    }
    return a.second > b.second;
}

const int64_t inf = 2e18;

int64_t div_up(int64_t a, int64_t b) {
    if (a < 0) {
        return a / b;
    }
    return (a + b - 1) / b;
}

long long take_photos(int n, int m, int k, vector<int> x, vector<int> y) {
    for (int i = 0; i < n; i++) {
        if (x[i] > y[i]) {
            swap(x[i], y[i]);
        }
    }
    vector<pair<int, int>> pairs;
    for (int i = 0; i < n; i++) {
        pairs.push_back({x[i], y[i]});
    }
    sort(pairs.begin(), pairs.end(), cmp);
    vector<pair<int, int>> new_pairs;
    new_pairs.push_back({-1, -1});
    int max_y = -1;
    for (int i = 0; i < n; i++) {
        if (max_y < pairs[i].second) {
            max_y = pairs[i].second;
            new_pairs.push_back(pairs[i]);
        }
    }
    n = new_pairs.size();
    vector<int64_t> l(n), r(n);
    for (int i = 0; i < n; i++) {
        l[i] = new_pairs[i].first;
        r[i] = new_pairs[i].second + 1;
    }
    k = min(k, n - 1);
    vector<int64_t> dp(n, inf);
    dp[0] = 0;
    for (int jumps = 0; jumps < k; jumps++) {
        vector<int64_t> a(n), b(n);
        for (int i = 0; i + 1 < n; i++) {
            a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
            b[i] = 2 * l[i + 1];
        }
        vector<int64_t> new_dp(n, inf);
        vector<pair<int64_t, int>> ch;
        ch.push_back({-1, jumps});
        for (int i = jumps + 1; i < n; i++) {
            int from = ch[upper_bound(ch.begin(), ch.end(), make_pair(r[i], n)) - ch.begin() - 1].second;
            new_dp[i] = r[i] * r[i] + a[from] - b[from] * r[i];
            if (i + 1 == n) {
                break;
            }
            while (!ch.empty()) {
                int last = ch.back().second;
                int64_t x = ch.back().first;
                if (a[last] - b[last] * x < a[i] - b[i] * x) {
                    break;
                }
                ch.pop_back();
            }
            int last = ch.back().second;
            int64_t x = div_up(a[i] - a[last], b[i] - b[last]);
            ch.push_back({x, i});
        }
        dp = new_dp;
    }
    return dp[n - 1];
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:54:74: error: no matching function for call to 'max(long long int, __gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type)'
   54 |             a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
      |                                                                          ^
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:54:74: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'})
   54 |             a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
      |                                                                          ^
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:54:74: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'})
   54 |             a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
      |                                                                          ^
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:54:74: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   54 |             a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
      |                                                                          ^
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:54:74: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   54 |             a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
      |                                                                          ^
aliens.cpp:54:102: error: no matching function for call to 'max(long long int, __gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type)'
   54 |             a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
      |                                                                                                      ^
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:54:102: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'})
   54 |             a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
      |                                                                                                      ^
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:54:102: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'})
   54 |             a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
      |                                                                                                      ^
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:54:102: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   54 |             a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
      |                                                                                                      ^
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:54:102: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   54 |             a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]);
      |                                                                                                      ^