| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 109365 | b2563125 | Boat (APIO16_boat) | C++14 | 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<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define int __int128
#define vel vector<long long>
#define V vector
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
int pr = 1000000007;
void uni(vel &a) {
vel ans(1, a[0]);
int n = a.size();
rep(i,n - 1) { if (a[i + 1] != a[i]) { ans.push_back(a[i + 1]); } }
a = ans;
}
int rui(int a, int n) {
if (n == 0) { return 1; }
int back = rui(a, n / 2);
back *= back; back %= pr;
if (n % 2 == 0) { return back; }
return (back*a) % pr;
}
int inv(int a) {
return rui(a, pr - 2);
}
signed main() {
int n; cin >> n;
vel a(n);
vel b(n);
vel all_time(1, 0);
rep(i, n) {
cin >> a[i] >> b[i]; b[i]++;
all_time.push_back(a[i]);
all_time.push_back(b[i]);
}
sort(all_time.begin(), all_time.end());
uni(all_time);
int sz = all_time.size();
vel gap(sz - 1);
rep(i, sz - 1) { gap[i] = all_time[i + 1] - all_time[i]; }
vel count(sz-1);
rep(i, n) {
a[i] = lower_bound(all_time.begin(), all_time.end(), a[i])-all_time.begin();
b[i] = lower_bound(all_time.begin(), all_time.end(), b[i])-all_time.begin();
rep(j, b[i] - a[i]) {
count[a[i] + j]++;
}
}
V<vel> com(sz-1);
rep(i, sz-1) {
int ba = 1;
rep(j, count[i]) {
ba *= gap[i] - j; ba %= pr;
ba *= inv(j + 1); ba %= pr;
com[i].push_back(ba);
}
}
V<V<vel>> dp1(2, V<vel>(sz-1,vel(n)));
vel now_count(sz - 1, 0);
rep(i, n) {
int now = i % 2;
int nex = (i + 1) % 2;
dp1[nex] = dp1[now];
int sum = 1;
rep(j, a[i]) {
rep(k, now_count[j]) {
sum += dp1[now][j][k] * com[j][k];
}
}
for (int j = a[i]; j < b[i]; j++) {
dp1[nex][j][0] += sum; dp1[nex][j][0] %= pr;
rep(k, now_count[j]) {
dp1[nex][j][k + 1] += dp1[now][j][k]; dp1[nex][j][k + 1] %= pr;
sum += dp1[now][j][k] * com[j][k];
}
sum += dp1[now][j][now_count[j]] * com[j][now_count[j]];
sum %= pr;
now_count[j]++;
}
}
int ans = 0;
rep(i, sz-1) {
rep(k, count[i]) {
ans += dp1[n%2][i][k] * com[i][k];
ans %= pr;
}
}
cout << ans << endl;
return 0;
}
Compilation message (stderr)
boat.cpp: In function 'int main()':
boat.cpp:28:13: error: no match for 'operator>>' (operand types are 'std::istream {aka std::basic_istream<char>}' and '__int128')
int n; cin >> n;
~~~~^~~~
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:120:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__istream_type& (*)(std::basic_istream<_CharT, _Traits>::__istream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(__istream_type& (*__pf)(__istream_type&))
^~~~~~~~
/usr/include/c++/7/istream:120:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: invalid conversion from '__int128' to 'std::basic_istream<char>::__istream_type& (*)(std::basic_istream<char>::__istream_type&) {aka std::basic_istream<char>& (*)(std::basic_istream<char>&)}' [-fpermissive]
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:124:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__ios_type& (*)(std::basic_istream<_CharT, _Traits>::__ios_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>; std::basic_istream<_CharT, _Traits>::__ios_type = std::basic_ios<char>] <near match>
operator>>(__ios_type& (*__pf)(__ios_type&))
^~~~~~~~
/usr/include/c++/7/istream:124:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: invalid conversion from '__int128' to 'std::basic_istream<char>::__ios_type& (*)(std::basic_istream<char>::__ios_type&) {aka std::basic_ios<char>& (*)(std::basic_ios<char>&)}' [-fpermissive]
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:131:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::ios_base& (*)(std::ios_base&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(ios_base& (*__pf)(ios_base&))
^~~~~~~~
/usr/include/c++/7/istream:131:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: invalid conversion from '__int128' to 'std::ios_base& (*)(std::ios_base&)' [-fpermissive]
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:168:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(bool& __n)
^~~~~~~~
/usr/include/c++/7/istream:168:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'bool&' to an rvalue of type 'bool'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:172:7: note: candidate: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>] <near match>
operator>>(short& __n);
^~~~~~~~
/usr/include/c++/7/istream:172:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'short int&' to an rvalue of type 'short int'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:175:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(unsigned short& __n)
^~~~~~~~
/usr/include/c++/7/istream:175:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'short unsigned int&' to an rvalue of type 'short unsigned int'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:179:7: note: candidate: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>] <near match>
operator>>(int& __n);
^~~~~~~~
/usr/include/c++/7/istream:179:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'int'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:182:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(unsigned int& __n)
^~~~~~~~
/usr/include/c++/7/istream:182:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'unsigned int&' to an rvalue of type 'unsigned int'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:186:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(long& __n)
^~~~~~~~
/usr/include/c++/7/istream:186:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'long int&' to an rvalue of type 'long int'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:190:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(unsigned long& __n)
^~~~~~~~
/usr/include/c++/7/istream:190:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'long unsigned int&' to an rvalue of type 'long unsigned int'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:195:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(long long& __n)
^~~~~~~~
/usr/include/c++/7/istream:195:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'long long int&' to an rvalue of type 'long long int'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:199:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(unsigned long long& __n)
^~~~~~~~
/usr/include/c++/7/istream:199:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'long long unsigned int&' to an rvalue of type 'long long unsigned int'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:214:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(float& __f)
^~~~~~~~
/usr/include/c++/7/istream:214:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'float&' to an rvalue of type 'float'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:218:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(double& __f)
^~~~~~~~
/usr/include/c++/7/istream:218:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'double&' to an rvalue of type 'double'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:222:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(long double& __f)
^~~~~~~~
/usr/include/c++/7/istream:222:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: cannot bind non-const lvalue reference of type 'long double&' to an rvalue of type 'long double'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:235:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>] <near match>
operator>>(void*& __p)
^~~~~~~~
/usr/include/c++/7/istream:235:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: invalid conversion from '__int128' to 'void*' [-fpermissive]
int n; cin >> n;
^
boat.cpp:28:16: error: cannot bind rvalue '(void*)((long int)n)' to 'void*&'
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:259:7: note: candidate: std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__streambuf_type*) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__streambuf_type = std::basic_streambuf<char>] <near match>
operator>>(__streambuf_type* __sb);
^~~~~~~~
/usr/include/c++/7/istream:259:7: note: conversion of argument 1 would be ill-formed:
boat.cpp:28:16: error: invalid conversion from '__int128' to 'std::basic_istream<char>::__streambuf_type* {aka std::basic_streambuf<char>*}' [-fpermissive]
int n; cin >> n;
^
boat.cpp:28:13: note: candidate: operator>>(int, __int128) <built-in>
int n; cin >> n;
~~~~^~~~
boat.cpp:28:13: note: no known conversion for argument 1 from 'std::istream {aka std::basic_istream<char>}' to 'int'
In file included from /usr/include/c++/7/string:53:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from boat.cpp:1:
/usr/include/c++/7/bits/basic_string.tcc:1465:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::basic_istream<_CharT, _Traits>& std::operator>>(std::basic_istream<_CharT, _Traits>&, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
operator>>(basic_istream<_CharT, _Traits>& __in,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.tcc:1465:5: note: template argument deduction/substitution failed:
boat.cpp:28:16: note: mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>' and '__int128'
int n; cin >> n;
^
In file included from /usr/include/c++/7/istream:991:0,
from /usr/include/c++/7/iostream:40,
from boat.cpp:1:
/usr/include/c++/7/bits/istream.tcc:963:5: note: candidate: template<class _CharT2, class _Traits2> std::basic_istream<_CharT, _Traits>& std::operator>>(std::basic_istream<_CharT, _Traits>&, _CharT2*)
operator>>(basic_istream<_CharT, _Traits>& __in, _CharT* __s)
^~~~~~~~
/usr/include/c++/7/bits/istream.tcc:963:5: note: template argument deduction/substitution failed:
boat.cpp:28:16: note: mismatched types '_CharT2*' and '__int128'
int n; cin >> n;
^
In file included from /usr/include/c++/7/istream:991:0,
from /usr/include/c++/7/iostream:40,
from boat.cpp:1:
/usr/include/c++/7/bits/istream.tcc:931:5: note: candidate: template<class _CharT, class _Traits> std::basic_istream<_CharT, _Traits>& std::operator>>(std::basic_istream<_CharT, _Traits>&, _CharT&)
operator>>(basic_istream<_CharT, _Traits>& __in, _CharT& __c)
^~~~~~~~
/usr/include/c++/7/bits/istream.tcc:931:5: note: template argument deduction/substitution failed:
boat.cpp:28:16: note: deduced conflicting types for parameter '_CharT' ('char' and '__int128')
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:756:5: note: candidate: template<class _Traits> std::basic_istream<char, _Traits>& std::operator>>(std::basic_istream<char, _Traits>&, unsigned char&)
operator>>(basic_istream<char, _Traits>& __in, unsigned char& __c)
^~~~~~~~
/usr/include/c++/7/istream:756:5: note: template argument deduction/substitution failed:
boat.cpp:28:16: note: cannot convert 'n' (type '__int128') to type 'unsigned char&'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:761:5: note: candidate: template<class _Traits> std::basic_istream<char, _Traits>& std::operator>>(std::basic_istream<char, _Traits>&, signed char&)
operator>>(basic_istream<char, _Traits>& __in, signed char& __c)
^~~~~~~~
/usr/include/c++/7/istream:761:5: note: template argument deduction/substitution failed:
boat.cpp:28:16: note: cannot convert 'n' (type '__int128') to type 'signed char&'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:803:5: note: candidate: template<class _Traits> std::basic_istream<char, _Traits>& std::operator>>(std::basic_istream<char, _Traits>&, unsigned char*)
operator>>(basic_istream<char, _Traits>& __in, unsigned char* __s)
^~~~~~~~
/usr/include/c++/7/istream:803:5: note: template argument deduction/substitution failed:
boat.cpp:28:16: note: cannot convert 'n' (type '__int128') to type 'unsigned char*'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:808:5: note: candidate: template<class _Traits> std::basic_istream<char, _Traits>& std::operator>>(std::basic_istream<char, _Traits>&, signed char*)
operator>>(basic_istream<char, _Traits>& __in, signed char* __s)
^~~~~~~~
/usr/include/c++/7/istream:808:5: note: template argument deduction/substitution failed:
boat.cpp:28:16: note: cannot convert 'n' (type '__int128') to type 'signed char*'
int n; cin >> n;
^
In file included from /usr/include/c++/7/iostream:40:0,
from boat.cpp:1:
/usr/include/c++/7/istream:980:5: note: candidate: template<class _Istream, class _Tp> typename std::enable_if<std::__and_<std::__not_<std::is_lvalue_reference<_Tp> >, std::__is_convertible_to_basic_istream<_Istream>, std::__is_extractable<typename std::__is_convertible_to_basic_istream<_Tp>::__istream_type, _Tp&&, void> >::value, typename std::__is_convertible_to_basic_istream<_Tp>::__istream_type>::type std::operator>>(_Istream&&, _Tp&&)
operator>>(_Istream&& __is, _Tp&& __x)
^~~~~~~~
/usr/include/c++/7/istream:980:5: note: template argument deduction/substitution failed:
/usr/include/c++/7/istream: In substitution of 'template<class _Istream, class _Tp> typename std::enable_if<std::__and_<std::__not_<std::is_lvalue_reference<_Tp> >, std::__is_convertible_to_basic_istream<_Istream>, std::__is_extractable<typename std::__is_convertible_to_basic_istream<_Tp>::__istream_type, _Tp&&, void> >::value, typename std::__is_convertible_to_basic_istream<_Tp>::__istream_type>::type std::operator