Submission #1365866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1365866		edo	Aliens (IOI16_aliens)	C++20	Compilation error	0 ms	0 KiB

aliens

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

using namespace std;
using ll = __int128_t;

struct Line {
  ll m, b;
  int cnt;
  pair<ll, int> get(ll x) const { return {m * x + b, cnt}; }
};

struct CHT {
  deque<Line> dq;
  bool bad(const Line &a, const Line &b, const Line &c) {
    return (b.b - a.b) * (b.m - c.m) >= (c.b - b.b) * (a.m - b.m);
  }
  void add(ll m, ll b, int cnt) {
    Line cur{m, b, cnt};
    while (dq.size() && dq.back().m == cur.m) {
      if (dq.back().b <= cur.b)
        return;
      dq.pop_back();
    }
    while (dq.size() >= 2 && bad(dq[dq.size() - 2], dq.back(), cur)) {
      dq.pop_back();
    }
    dq.push_back(cur);
  }

  pair<ll, int> qry(ll x) {
    while (dq.size() >= 2 && dq[1].get(x) < dq[0].get(x)) {
      dq.pop_front();
    }
    return dq[0].get(x);
  }
};
vector<pair<int, int>> pt;
pair<int, ll> calc(ll penal) {
  CHT cht;
  pair<ll, int> dp = {0, 0};
  for (int i = 0; i < pt.size(); ++i) {
    auto &[L, R] = pt[i];
    ll over = 0;
    if (i) {
      over = max(over, 1ll * pt[i - 1].second - L + 1);
    }
    cht.add(-2 * L, dp.first - over * over + L * L, dp.second);
    ll x = R + 1;
    dp = cht.qry(x);
    dp.first += x * x + penal;
    dp.second++;
  }
  return dp;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  {
    vector<pair<int, int>> tmp(n);
    for (int i = 0; i < n; ++i) {
      tmp[i] = minmax(r[i], c[i]);
    }

    ranges::sort(tmp);
    for (auto &[L, R] : tmp) {
      if (pt.size() && R <= pt.back().second) {
        continue;
      }
      pt.push_back({L, R});
    }
  }

  long long lo = 0, hi = 1ll * m * m, ans;
  while (hi - lo + 1) {
    ll mid = (lo + hi) / 2;
    auto dp = calc(mid);
    if (dp.second <= k) {
      hi = mid - 1;
      ans = dp.first;
    } else
      lo = mid + 1;
  }

  return ans - lo * k;
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<int, __int128> calc(ll)':
aliens.cpp:46:17: error: no matching function for call to 'max(ll&, long long int)'
   46 |       over = max(over, 1ll * pt[i - 1].second - L + 1);
      |              ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/vector:62,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
aliens.cpp:46:17: note:   deduced conflicting types for parameter 'const _Tp' ('__int128' and 'long long int')
   46 |       over = max(over, 1ll * pt[i - 1].second - L + 1);
      |              ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
aliens.cpp:46:17: note:   deduced conflicting types for parameter 'const _Tp' ('__int128' and 'long long int')
   46 |       over = max(over, 1ll * pt[i - 1].second - L + 1);
      |              ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from aliens.cpp:2:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
aliens.cpp:46:17: note:   mismatched types 'std::initializer_list<_Tp>' and '__int128'
   46 |       over = max(over, 1ll * pt[i - 1].second - L + 1);
      |              ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
aliens.cpp:46:17: note:   mismatched types 'std::initializer_list<_Tp>' and '__int128'
   46 |       over = max(over, 1ll * pt[i - 1].second - L + 1);
      |              ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~