Submission #330737

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

aliens

#include <bits/stdc++.h>

using namespace std;

#define int long long

const long long INFLL = 1e18;

pair<long long, long long> calc(int n, long long M, vector<int> l, vector<int> r)
{
    vector<long long> dp(n, INFLL);
    vector<long long> bl(n, INFLL);
    for (int i = 0; i < n; i++)
        dp[i] = M + 1ll * (r[i] - l[0] + 1) * (r[i] - l[0] + 1), bl[i] = 1;
    struct line{
        long long k, b, id;
    };
    vector<line> convex;
    for (int i = 0; i < n; i++)
    {
        long long res = 1ll * r[i] * r[i];
        long long d = INFLL, used = 0;
        for (auto e : convex)
        {
            if (e.b + e.k * r[i] < d)
                d = e.b + e.k * r[i], used = INFLL;
            if (e.b + e.k * r[i] == d && bl[e.id] < used)
                used = bl[e.id];
        }
        res += d;
        if (res < dp[i])
            dp[i] = res, bl[i] = used + 1;
        if (i + 1 < n)
        {
            long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
            long long k = 2 * (1 - l[i + 1]);
            convex.push_back({k, b, i});
        }
    }
    //cout << M << " " << dp[n - 1] << " " << bl[n - 1] << endl;
    return {dp[n - 1], bl[n - 1]};
}

long long take_photos(int n, int m, int k, vector<int> l, vector<int> r)
{
    vector<int> cv(m);
    for (int i = 0; i < m; i++)
    {
        cv[i] = i + 1;
    }
    for (int i = 0; i < n; i++)
    {
        int x = min(l[i], r[i]);
        int y = max(l[i], r[i]);
        cv[y] = min(cv[y], x);
    }
    l.clear();
    r.clear();
    for (int i = 0; i < m; i++)
    {
        if (cv[i] <= i)
        {
            while (l.size() && l.back() >= cv[i])
                l.pop_back(), r.pop_back();
            l.push_back(cv[i]), r.push_back(i);
        }
    }
    n = l.size();
    //for (int i = 0; i < l.size(); i++)
    //    cout << l[i] << " " << r[i] << endl;
    long long L = 0, R = m * m + 222;
    long long ans = INFLL;
    k = min(k, n);
    while (L + 1 < R)
    {
        long long M = (L + R) / 2;
        if (calc(n, M, l, r).second >= k)
            L = M;
        else
            R = M;
    }
    for (int d = R - 1; d <= R; d++)
    {
        pair<long long, long long> res = calc(n, d, l, r);
        //cout << res.first << " " << res.second << " " << d << " " << k << endl;
        if (res.second <= k)
            ans = min(ans, res.first - k * d);
    }
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, long long int> calc(long long int, long long int, std::vector<long long int>, std::vector<long long int>)':
aliens.cpp:35:118: error: no matching function for call to 'max(int, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type)'
   35 |             long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
      |                                                                                                                      ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from aliens.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  222 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note:   template argument deduction/substitution failed:
aliens.cpp:35:118: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   35 |             long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
      |                                                                                                                      ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from aliens.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  268 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note:   template argument deduction/substitution failed:
aliens.cpp:35:118: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   35 |             long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
      |                                                                                                                      ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from aliens.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3456 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
aliens.cpp:35:118: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   35 |             long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
      |                                                                                                                      ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from aliens.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
aliens.cpp:35:118: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   35 |             long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
      |                                                                                                                      ^
aliens.cpp:35:148: error: no matching function for call to 'max(int, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type)'
   35 |             long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
      |                                                                                                                                                    ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from aliens.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  222 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note:   template argument deduction/substitution failed:
aliens.cpp:35:148: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   35 |             long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
      |                                                                                                                                                    ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from aliens.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  268 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note:   template argument deduction/substitution failed:
aliens.cpp:35:148: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   35 |             long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
      |                                                                                                                                                    ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from aliens.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3456 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
aliens.cpp:35:148: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   35 |             long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
      |                                                                                                                                                    ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from aliens.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
aliens.cpp:35:148: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   35 |             long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
      |                                                                                                                                                    ^