| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1346888 | kaze666 | Fish (IOI08_fish) | C++20 | Compilation error | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define int int64_t
int n, k, m, N;
vector<int> t, cnt, longest;
vector<vector<int>> v;
void build() {
for (int i = 0; i < N; i++) t[i + N] = cnt[i] + 1;
for (int i = N - 1; i > 0; i--) t[i] = t[i << 1] * t[i << 1 | 1] % m;
}
void update(int p, int val) {
p += N;
t[p] = t[p] + val;
if (t[p] < 0) t[p] += m;
for (p >>= 1; p > 0; p >>= 1) t[p] = t[p << 1] * t[p << 1 | 1] % m;
}
int query(int l, int r) {
int res = 1;
for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = res * t[l++] % m;
if (r & 1) res = res * t[--r] % m;
}
return res;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k >> m;
v.assign(k, vector<int>());
for (int i = 0; i < n; i++) {
int x, y; cin >> x >> y;
v[--y].push_back(x);
}
for (int i = 0; i < k; i++) sort(all(v[i]));
sort(v, v + k, [](vector<int>& a, vector<int>& b) {
return a.back() > b.back();
});
for (int i = k - 1; i >= 0; i--) longest.push_back(v[i].back());
cnt.assign(k, 0);
for (int i = 0; i < k; i++) cnt[i] = sz(v[i]);
N = k;
t.assign(2 * N, 1);
build();
priority_queue<pair<int,int>> pq;
for (int i = 0; i < k; i++) {
for (int x : v[i]) {
pq.emplace(x, i);
}
}
vector<vector<int>> dp(k, vector<int>(2, 0));
for (int i = 0; i < k; i++) {
int mx = v[i].back();
while (!pq.empty() && pq.top().first > mx / 2) {
auto top = pq.top(); pq.pop();
int ttype = top.second;
cnt[ttype]--;
update(ttype, -1);
}
int c = upper_bound(all(v[i]), mx / 2) - v[i].begin();
dp[i][0] = 1;
dp[i][1] = c;
dp[i][0] = dp[i][0] * query(i + 1, k) % m;
dp[i][1] = dp[i][1] * query(i + 1, k) % m;
if (c < sz(v[i])) {
int idx = lower_bound(all(longest), 2 * v[i][c]) - longest.begin();
int L = k - idx, R = i - 1;
if (L <= R) {
dp[i][0] = dp[i][0] * query(L, R + 1) % m;
}
}
}
int ans = 0;
for (int i = 0; i < k; i++) ans = (ans + dp[i][0] + dp[i][1]) % m;
cout << ans << '\n';
return 0;
}Compilation message (stderr)
fish.cpp: In function 'int32_t main()':
fish.cpp:38:13: error: no match for 'operator+' (operand types are 'std::vector<std::vector<long int> >' and 'int64_t' {aka 'long int'})
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ~ ^ ~
| | |
| | int64_t {aka long int}
| std::vector<std::vector<long int> >
In file included from /usr/include/c++/13/bits/stl_algobase.h:67,
from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from fish.cpp:1:
/usr/include/c++/13/bits/stl_iterator.h:634:5: note: candidate: 'template<class _Iterator> constexpr std::reverse_iterator<_IteratorL> std::operator+(typename reverse_iterator<_IteratorL>::difference_type, const reverse_iterator<_IteratorL>&)'
634 | operator+(typename reverse_iterator<_Iterator>::difference_type __n,
| ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:634:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: mismatched types 'const std::reverse_iterator<_IteratorL>' and 'int64_t' {aka 'long int'}
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/stl_iterator.h:1808:5: note: candidate: 'template<class _Iterator> constexpr std::move_iterator<_IteratorL> std::operator+(typename move_iterator<_IteratorL>::difference_type, const move_iterator<_IteratorL>&)'
1808 | operator+(typename move_iterator<_Iterator>::difference_type __n,
| ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1808:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: mismatched types 'const std::move_iterator<_IteratorL>' and 'int64_t' {aka 'long int'}
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
In file included from /usr/include/c++/13/string:54,
from /usr/include/c++/13/bitset:52,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52:
/usr/include/c++/13/bits/basic_string.h:3553:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
3553 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3553:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/basic_string.h:3571:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
3571 | operator+(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3571:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: mismatched types 'const _CharT*' and 'std::vector<std::vector<long int> >'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/basic_string.h:3590:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
3590 | operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs)
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3590:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int64_t' {aka 'long int'}
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/basic_string.h:3607:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
3607 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3607:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/basic_string.h:3625:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, _CharT)'
3625 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3625:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/basic_string.h:3637:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
3637 | operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3637:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/basic_string.h:3644:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, __cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
3644 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3644:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/basic_string.h:3651:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, __cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
3651 | operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3651:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/basic_string.h:3674:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, __cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
3674 | operator+(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3674:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: mismatched types 'const _CharT*' and 'std::vector<std::vector<long int> >'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/basic_string.h:3681:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, __cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
3681 | operator+(_CharT __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3681:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int64_t' {aka 'long int'}
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/basic_string.h:3688:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const _CharT*)'
3688 | operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3688:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/basic_string.h:3695:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, _CharT)'
3695 | operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3695:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
In file included from /usr/include/c++/13/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127:
/usr/include/c++/13/complex:335:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator+(const complex<_Tp>&, const complex<_Tp>&)'
335 | operator+(const complex<_Tp>& __x, const complex<_Tp>& __y)
| ^~~~~~~~
/usr/include/c++/13/complex:335:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::complex<_Tp>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/complex:344:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator+(const complex<_Tp>&, const _Tp&)'
344 | operator+(const complex<_Tp>& __x, const _Tp& __y)
| ^~~~~~~~
/usr/include/c++/13/complex:344:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::complex<_Tp>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/complex:353:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator+(const _Tp&, const complex<_Tp>&)'
353 | operator+(const _Tp& __x, const complex<_Tp>& __y)
| ^~~~~~~~
/usr/include/c++/13/complex:353:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: mismatched types 'const std::complex<_Tp>' and 'int64_t' {aka 'long int'}
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/complex:454:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator+(const complex<_Tp>&)'
454 | operator+(const complex<_Tp>& __x)
| ^~~~~~~~
/usr/include/c++/13/complex:454:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::complex<_Tp>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
In file included from /usr/include/c++/13/valarray:605,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:166:
/usr/include/c++/13/bits/valarray_after.h:405:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__plus, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__plus, typename _Dom1::value_type>::result_type> std::operator+(const _Expr<_Dom1, typename _Dom1::value_type>&, const _Expr<_Dom2, typename _Dom2::value_type>&)'
405 | _DEFINE_EXPR_BINARY_OPERATOR(+, struct std::__plus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:405:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/valarray_after.h:405:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__plus, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__plus, typename _Dom1::value_type>::result_type> std::operator+(const _Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
405 | _DEFINE_EXPR_BINARY_OPERATOR(+, struct std::__plus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:405:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/valarray_after.h:405:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__plus, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__plus, typename _Dom1::value_type>::result_type> std::operator+(const typename _Dom::value_type&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
405 | _DEFINE_EXPR_BINARY_OPERATOR(+, struct std::__plus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:405:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int64_t' {aka 'long int'}
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/valarray_after.h:405:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__plus, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__plus, typename _Dom1::value_type>::result_type> std::operator+(const _Expr<_Dom1, typename _Dom1::value_type>&, const valarray<typename _Dom::value_type>&)'
405 | _DEFINE_EXPR_BINARY_OPERATOR(+, struct std::__plus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:405:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/bits/valarray_after.h:405:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__plus, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__plus, typename _Dom1::value_type>::result_type> std::operator+(const valarray<typename _Dom::value_type>&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
405 | _DEFINE_EXPR_BINARY_OPERATOR(+, struct std::__plus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:405:5: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int64_t' {aka 'long int'}
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/valarray:1196:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__plus, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__plus, _Tp>::result_type> std::operator+(const valarray<_Tp>&, const valarray<_Tp>&)'
1196 | _DEFINE_BINARY_OPERATOR(+, __plus)
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1196:1: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::valarray<_Tp>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/valarray:1196:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__plus, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__plus, _Tp>::result_type> std::operator+(const valarray<_Tp>&, const typename valarray<_Tp>::value_type&)'
1196 | _DEFINE_BINARY_OPERATOR(+, __plus)
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1196:1: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: 'std::vector<std::vector<long int> >' is not derived from 'const std::valarray<_Tp>'
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^
/usr/include/c++/13/valarray:1196:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__plus, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__plus, _Tp>::result_type> std::operator+(const typename valarray<_Tp>::value_type&, const valarray<_Tp>&)'
1196 | _DEFINE_BINARY_OPERATOR(+, __plus)
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1196:1: note: template argument deduction/substitution failed:
fish.cpp:38:15: note: mismatched types 'const std::valarray<_Tp>' and 'int64_t' {aka 'long int'}
38 | sort(v, v + k, [](vector<int>& a, vector<int>& b) {
| ^