| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 842506 | CodePlatina | Overtaking (IOI23_overtaking) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "overtaking.h"
#include <algorithm>
#include <iostream>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ff first
#define ss second
using namespace std;
const long long INF = (long long)2e18 + 17;
int X;
vector<int> S;
vector<pll> A;
vector<vector<pll>> B;
vector<vector<long long>> MX;
int sp[1'000'005][21];
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
::X = X;
::S = S;
for(int i = 0; i < N; ++i) if(W[i] > X) A.push_back({ T[i], W[i] });
N = A.size();
sort(A.begin(), A.end());
B.push_back(A);
for(int i = 1; i < M; ++i)
{
int t = S[i] - S[i - 1];
vector<pll> C;
vector<long long> D;
long long mx = -INF;
long long prmx = -INF;
for(int j = 0; j < N; ++j)
{
if(j && B.back()[j - 1].ff < B.back()[j].ff)
mx = max(mx, prmx), prmx = -INF;
D.push_back(mx);
long long cur = B.back()[j].ff + B.back()[j].ss * t;
C.push_back({ max(mx, cur), B.back()[j].ss });
prmx = max(prmx, cur);
}
D.push_back(max(mx, prmx));
sort(C.begin(), C.end());
B.push_back(C);
MX.push_back(D);
}
for(int i = 0; i < M; ++i)
{
for(int j = 0; j < N; ++j)
{
int cur = i * N + j;
int s = i, e = M;
while(s + 1 < e)
{
int mid = s + e >> 1;
if(j == 0 || B[mid][j - 1].ff < B[i][j].ff + 1ll * X * (S[mid] - S[i])) - B[mid].begin() == j) s = mid;
else e = mid;
}
if(e < M)
sp[cur][0] = e * N + (lower_bound(B[e].begin(), B[e].end(), pll{MX[s][j], -INF}) - B[e].begin());
else sp[cur][0] = cur;
}
}
for(int j = 1; j <= 20; ++j) for(int i = 0; i < N * M; ++i)
sp[i][j] = sp[sp[i][j - 1]][j - 1];
// for(auto i : B)
// {
// for(auto j : i) cout << "(" << j.ff << ", " << j.ss << ")" << ' ';
// cout << endl;
// }
}
long long arrival_time(long long Y)
{
int M = B.size(), N = B[0].size();
int ind = lower_bound(B[0].begin(), B[0].end(), pll{Y, -INF}) - B[0].begin();
int s = 0, e = M;
while(s + 1 < e)
{
int mid = s + e >> 1;
if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
else e = mid;
}
if(e == M) return Y + 1ll * X * S.back();
// cout << e << endl;
ind = e * N + (lower_bound(B[e].begin(), B[e].end(), pll{MX[s][ind], -INF}) - B[e].begin());
ind = sp[ind][20];
int i = ind / N, j = ind % N;
// cout << i << ' ' << j << endl;
return B[i][j].ff + 1ll * X * (S.back() - S[i]);
}
Compilation message (stderr)
overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:57:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid = s + e >> 1;
| ~~^~~
overtaking.cpp:58:89: error: no match for 'operator-' (operand type is 'std::vector<std::pair<long long int, long long int> >::iterator')
58 | if(j == 0 || B[mid][j - 1].ff < B[i][j].ff + 1ll * X * (S[mid] - S[i])) - B[mid].begin() == j) s = mid;
| ^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from overtaking.h:1,
from overtaking.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1026:7: note: candidate: '__gnu_cxx::__normal_iterator<_Iterator, _Container> __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator-(__gnu_cxx::__normal_iterator<_Iterator, _Container>::difference_type) const [with _Iterator = std::pair<long long int, long long int>*; _Container = std::vector<std::pair<long long int, long long int> >; __gnu_cxx::__normal_iterator<_Iterator, _Container>::difference_type = long int]'
1026 | operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1026:7: note: candidate expects 1 argument, 0 provided
/usr/include/c++/10/bits/stl_iterator.h:500:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
500 | operator-(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:500:5: note: template argument deduction/substitution failed:
overtaking.cpp:58:104: note: 'std::vector<std::pair<long long int, long long int> >::iterator' is not derived from 'const std::reverse_iterator<_Iterator>'
58 | if(j == 0 || B[mid][j - 1].ff < B[i][j].ff + 1ll * X * (S[mid] - S[i])) - B[mid].begin() == j) s = mid;
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from overtaking.h:1,
from overtaking.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1533:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1533 | operator-(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1533:5: note: template argument deduction/substitution failed:
overtaking.cpp:58:104: note: 'std::vector<std::pair<long long int, long long int> >::iterator' is not derived from 'const std::move_iterator<_IteratorL>'
58 | if(j == 0 || B[mid][j - 1].ff < B[i][j].ff + 1ll * X * (S[mid] - S[i])) - B[mid].begin() == j) s = mid;
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from overtaking.h:1,
from overtaking.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1164:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> decltype ((__lhs.base() - __rhs.base())) __gnu_cxx::operator-(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
1164 | operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1164:5: note: template argument deduction/substitution failed:
overtaking.cpp:58:104: note: candidate expects 2 arguments, 1 provided
58 | if(j == 0 || B[mid][j - 1].ff < B[i][j].ff + 1ll * X * (S[mid] - S[i])) - B[mid].begin() == j) s = mid;
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from overtaking.h:1,
from overtaking.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1177:5: note: candidate: 'template<class _Iterator, class _Container> typename __gnu_cxx::__normal_iterator<_Iterator, _Container>::difference_type __gnu_cxx::operator-(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
1177 | operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1177:5: note: template argument deduction/substitution failed:
overtaking.cpp:58:104: note: candidate expects 2 arguments, 1 provided
58 | if(j == 0 || B[mid][j - 1].ff < B[i][j].ff + 1ll * X * (S[mid] - S[i])) - B[mid].begin() == j) s = mid;
| ^
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:85:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int mid = s + e >> 1;
| ~~^~~
overtaking.cpp:86:40: error: no match for 'operator<' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} and 'long long int')
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from overtaking.h:1,
from overtaking.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:489:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
489 | operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:489:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: mismatched types 'const std::pair<_T1, _T2>' and 'long long int'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from overtaking.h:1,
from overtaking.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:366:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
366 | operator<(const reverse_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:366:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from overtaking.h:1,
from overtaking.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:404:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
404 | operator<(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:404:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from overtaking.h:1,
from overtaking.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1451:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1451 | operator<(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1451:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::move_iterator<_IteratorL>'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from overtaking.h:1,
from overtaking.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1507:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
1507 | operator<(const move_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1507:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::move_iterator<_IteratorL>'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/10/vector:67,
from overtaking.h:1,
from overtaking.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1930:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator<(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&)'
1930 | operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1930:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::vector<_Tp, _Alloc>'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/10/tuple:39,
from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from overtaking.cpp:2:
/usr/include/c++/10/array:284:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> bool std::operator<(const std::array<_Tp, _Nm>&, const std::array<_Tp, _Nm>&)'
284 | operator<(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b)
| ^~~~~~~~
/usr/include/c++/10/array:284:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::array<_Tp, _Nm>'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from overtaking.cpp:2:
/usr/include/c++/10/tuple:1435:5: note: candidate: 'template<class ... _TElements, class ... _UElements> constexpr bool std::operator<(const std::tuple<_Tps ...>&, const std::tuple<_UTypes ...>&)'
1435 | operator<(const tuple<_TElements...>& __t,
| ^~~~~~~~
/usr/include/c++/10/tuple:1435:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::tuple<_Tps ...>'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/10/bits/node_handle.h:39,
from /usr/include/c++/10/bits/hashtable.h:37,
from /usr/include/c++/10/unordered_map:46,
from /usr/include/c++/10/functional:61,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from overtaking.cpp:2:
/usr/include/c++/10/optional:1003:5: note: candidate: 'template<class _Tp, class _Up> constexpr std::__optional_relop_t<decltype ((declval<_Tp>() < declval<_Up>()))> std::operator<(const std::optional<_Tp>&, const std::optional<_Up>&)'
1003 | operator<(const optional<_Tp>& __lhs, const optional<_Up>& __rhs)
| ^~~~~~~~
/usr/include/c++/10/optional:1003:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::optional<_Tp>'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/10/bits/node_handle.h:39,
from /usr/include/c++/10/bits/hashtable.h:37,
from /usr/include/c++/10/unordered_map:46,
from /usr/include/c++/10/functional:61,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from overtaking.cpp:2:
/usr/include/c++/10/optional:1071:5: note: candidate: 'template<class _Tp> constexpr bool std::operator<(const std::optional<_Tp>&, std::nullopt_t)'
1071 | operator<(const optional<_Tp>& /* __lhs */, nullopt_t) noexcept
| ^~~~~~~~
/usr/include/c++/10/optional:1071:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::optional<_Tp>'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/10/bits/node_handle.h:39,
from /usr/include/c++/10/bits/hashtable.h:37,
from /usr/include/c++/10/unordered_map:46,
from /usr/include/c++/10/functional:61,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from overtaking.cpp:2:
/usr/include/c++/10/optional:1076:5: note: candidate: 'template<class _Tp> constexpr bool std::operator<(std::nullopt_t, const std::optional<_Tp>&)'
1076 | operator<(nullopt_t, const optional<_Tp>& __rhs) noexcept
| ^~~~~~~~
/usr/include/c++/10/optional:1076:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: mismatched types 'const std::optional<_Tp>' and 'long long int'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/10/bits/node_handle.h:39,
from /usr/include/c++/10/bits/hashtable.h:37,
from /usr/include/c++/10/unordered_map:46,
from /usr/include/c++/10/functional:61,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from overtaking.cpp:2:
/usr/include/c++/10/optional:1137:5: note: candidate: 'template<class _Tp, class _Up> constexpr std::__optional_relop_t<decltype ((declval<_Tp>() < declval<_Up>()))> std::operator<(const std::optional<_Tp>&, const _Up&)'
1137 | operator<(const optional<_Tp>& __lhs, const _Up& __rhs)
| ^~~~~~~~
/usr/include/c++/10/optional:1137:5: note: template argument deduction/substitution failed:
overtaking.cpp:86:61: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::optional<_Tp>'
86 | if(ind == 0 || B[mid][ind - 1] < Y + 1ll * X * S[mid]) s = mid;
| ^
In file included from /usr/include/c++/1