| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 276218 | 2020-08-20T11:33:54 Z | anubhavdhar | Building Bridges (CEOI17_building) | C++11 | Compilation error |
0 ms | 0 KB |
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
using namespace std;
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;
int N;
ll dp[MAXN], pre[MAXN], h[MAXN];
struct line //mx + c
{
mutable ll m, c, p;
bool operator < (const line& o) const {return m < o.m;}
bool operator < (ll x) const {return p < x;}
};
struct CHT_black_box : multiset<line, less<>>
{
int mode;
void set_mode(string S) {mode = (S[1] == 'i' || S[1] == 'I') ? -1 : 1;}
ll div(ll a, ll b) {return a/b - ((a^b) < 0 && a%b);}
bool isect(iterator x, iterator y)
{
if(y == end()){x->p = INF; return false;}
if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
else x->p = div((y->c - x->c),(x->m - y->m));
return (x->p >= y->p);
}
void add(ll slope, ll intercept)
{
auto z = insert({mode * slope, mode * intercept, 0}), y = z++, x = y;
while(isect(y, z)) z = erase(z);
if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
}
ll query(ll x)
{
assert(!empty());
auto l = *lower_bound(x);
return mode * (l.m * x + l.c);
}
}box;
signed main()
{
/*
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
*/
ll w;
cin>>N;
F0R(i, N)
cin>>h[i];
F0R(i, N)
cin>>w, pre[i] = w + ((i == 0) ? 0 : pre[i-1]);
box.set_mode("min");
dp[0] = 0;
box.add( - 2*h[0], h[0]*h[0] + dp[0] - pre[0]);
F0Re(i, N-1)
{
dp[i] = (h[i] * h[i] + pre[i-1]) + box.query(h[i]);
box.add(- 2*h[i], h[i]*h[i] + dp[i] - pre[i]);
}
//F0R(i, N)
// cout<<"dp["<<i<<"] = "<<dp[i]<<'\n';
cout<<dp[N-1]<<'\n';
return 0;
}
Compilation message
building.cpp:51:43: error: wrong number of template arguments (0, should be 1)
51 | struct CHT_black_box : multiset<line, less<>>
| ^
In file included from /usr/include/c++/9/string:48,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from building.cpp:1:
/usr/include/c++/9/bits/stl_function.h:381:12: note: provided for 'template<class _Tp> struct std::less'
381 | struct less : public binary_function<_Tp, _Tp, bool>
| ^~~~
building.cpp:51:44: error: template argument 2 is invalid
51 | struct CHT_black_box : multiset<line, less<>>
| ^~
building.cpp:56:13: error: 'iterator' is not a type
56 | bool isect(iterator x, iterator y)
| ^~~~~~~~
building.cpp:56:25: error: 'iterator' is not a type
56 | bool isect(iterator x, iterator y)
| ^~~~~~~~
building.cpp: In member function 'bool CHT_black_box::isect(int, int)':
building.cpp:58:15: error: no matching function for call to 'end()'
58 | if(y == end()){x->p = INF; return false;}
| ^
In file included from /usr/include/c++/9/bits/range_access.h:36,
from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from building.cpp:1:
/usr/include/c++/9/initializer_list:99:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
99 | end(initializer_list<_Tp> __ils) noexcept
| ^~~
/usr/include/c++/9/initializer_list:99:5: note: template argument deduction/substitution failed:
building.cpp:58:15: note: candidate expects 1 argument, 0 provided
58 | if(y == end()){x->p = INF; return false;}
| ^
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from building.cpp:1:
/usr/include/c++/9/bits/range_access.h:68:5: note: candidate: 'template<class _Container> decltype (__cont.end()) std::end(_Container&)'
68 | end(_Container& __cont) -> decltype(__cont.end())
| ^~~
/usr/include/c++/9/bits/range_access.h:68:5: note: template argument deduction/substitution failed:
building.cpp:58:15: note: candidate expects 1 argument, 0 provided
58 | if(y == end()){x->p = INF; return false;}
| ^
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from building.cpp:1:
/usr/include/c++/9/bits/range_access.h:78:5: note: candidate: 'template<class _Container> decltype (__cont.end()) std::end(const _Container&)'
78 | end(const _Container& __cont) -> decltype(__cont.end())
| ^~~
/usr/include/c++/9/bits/range_access.h:78:5: note: template argument deduction/substitution failed:
building.cpp:58:15: note: candidate expects 1 argument, 0 provided
58 | if(y == end()){x->p = INF; return false;}
| ^
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from building.cpp:1:
/usr/include/c++/9/bits/range_access.h:97:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> _Tp* std::end(_Tp (&)[_Nm])'
97 | end(_Tp (&__arr)[_Nm])
| ^~~
/usr/include/c++/9/bits/range_access.h:97:5: note: template argument deduction/substitution failed:
building.cpp:58:15: note: candidate expects 1 argument, 0 provided
58 | if(y == end()){x->p = INF; return false;}
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
from building.cpp:1:
/usr/include/c++/9/valarray:1234:5: note: candidate: 'template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)'
1234 | end(valarray<_Tp>& __va)
| ^~~
/usr/include/c++/9/valarray:1234:5: note: template argument deduction/substitution failed:
building.cpp:58:15: note: candidate expects 1 argument, 0 provided
58 | if(y == end()){x->p = INF; return false;}
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
from building.cpp:1:
/usr/include/c++/9/valarray:1244:5: note: candidate: 'template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)'
1244 | end(const valarray<_Tp>& __va)
| ^~~
/usr/include/c++/9/valarray:1244:5: note: template argument deduction/substitution failed:
building.cpp:58:15: note: candidate expects 1 argument, 0 provided
58 | if(y == end()){x->p = INF; return false;}
| ^
building.cpp:58:19: error: base operand of '->' is not a pointer
58 | if(y == end()){x->p = INF; return false;}
| ^~
building.cpp:59:7: error: base operand of '->' is not a pointer
59 | if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
| ^~
building.cpp:59:15: error: base operand of '->' is not a pointer
59 | if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
| ^~
building.cpp:59:21: error: base operand of '->' is not a pointer
59 | if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
| ^~
building.cpp:59:29: error: base operand of '->' is not a pointer
59 | if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
| ^~
building.cpp:59:36: error: base operand of '->' is not a pointer
59 | if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
| ^~
building.cpp:60:9: error: base operand of '->' is not a pointer
60 | else x->p = div((y->c - x->c),(x->m - y->m));
| ^~
building.cpp:60:21: error: base operand of '->' is not a pointer
60 | else x->p = div((y->c - x->c),(x->m - y->m));
| ^~
building.cpp:60:28: error: base operand of '->' is not a pointer
60 | else x->p = div((y->c - x->c),(x->m - y->m));
| ^~
building.cpp:60:35: error: base operand of '->' is not a pointer
60 | else x->p = div((y->c - x->c),(x->m - y->m));
| ^~
building.cpp:60:42: error: base operand of '->' is not a pointer
60 | else x->p = div((y->c - x->c),(x->m - y->m));
| ^~
building.cpp:61:12: error: base operand of '->' is not a pointer
61 | return (x->p >= y->p);
| ^~
building.cpp:61:20: error: base operand of '->' is not a pointer
61 | return (x->p >= y->p);
| ^~
building.cpp: In member function 'void CHT_black_box::add(long long int, long long int)':
building.cpp:65:12: error: 'insert' was not declared in this scope; did you mean 'isect'?
65 | auto z = insert({mode * slope, mode * intercept, 0}), y = z++, x = y;
| ^~~~~~
| isect
building.cpp:66:15: error: 'y' was not declared in this scope
66 | while(isect(y, z)) z = erase(z);
| ^
building.cpp:66:26: error: 'erase' was not declared in this scope
66 | while(isect(y, z)) z = erase(z);
| ^~~~~
building.cpp:67:6: error: 'x' was not declared in this scope
67 | if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^
building.cpp:67:17: error: no matching function for call to 'begin()'
67 | if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^
In file included from /usr/include/c++/9/bits/range_access.h:36,
from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from building.cpp:1:
/usr/include/c++/9/initializer_list:89:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
89 | begin(initializer_list<_Tp> __ils) noexcept
| ^~~~~
/usr/include/c++/9/initializer_list:89:5: note: template argument deduction/substitution failed:
building.cpp:67:17: note: candidate expects 1 argument, 0 provided
67 | if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from building.cpp:1:
/usr/include/c++/9/bits/range_access.h:48:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&)'
48 | begin(_Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/9/bits/range_access.h:48:5: note: template argument deduction/substitution failed:
building.cpp:67:17: note: candidate expects 1 argument, 0 provided
67 | if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from building.cpp:1:
/usr/include/c++/9/bits/range_access.h:58:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(const _Container&)'
58 | begin(const _Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/9/bits/range_access.h:58:5: note: template argument deduction/substitution failed:
building.cpp:67:17: note: candidate expects 1 argument, 0 provided
67 | if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from building.cpp:1:
/usr/include/c++/9/bits/range_access.h:87:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> _Tp* std::begin(_Tp (&)[_Nm])'
87 | begin(_Tp (&__arr)[_Nm])
| ^~~~~
/usr/include/c++/9/bits/range_access.h:87:5: note: template argument deduction/substitution failed:
building.cpp:67:17: note: candidate expects 1 argument, 0 provided
67 | if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
from building.cpp:1:
/usr/include/c++/9/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
1214 | begin(valarray<_Tp>& __va)
| ^~~~~
/usr/include/c++/9/valarray:1214:5: note: template argument deduction/substitution failed:
building.cpp:67:17: note: candidate expects 1 argument, 0 provided
67 | if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
from building.cpp:1:
/usr/include/c++/9/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
1224 | begin(const valarray<_Tp>& __va)
| ^~~~~
/usr/include/c++/9/valarray:1224:5: note: template argument deduction/substitution failed:
building.cpp:67:17: note: candidate expects 1 argument, 0 provided
67 | if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^
building.cpp:67:33: error: 'y' was not declared in this scope
67 | if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^
building.cpp:67:50: error: 'erase' was not declared in this scope
67 | if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^~~~~
building.cpp:68:10: error: 'y' was not declared in this scope
68 | while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
| ^
building.cpp:68:12: error: 'x' was not declared in this scope
68 | while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
| ^
building.cpp:68:24: error: no matching function for call to 'begin()'
68 | while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
| ^
In file included from /usr/include/c++/9/bits/range_access.h:36,
from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from building.cpp:1:
/usr/include/c++/9/initializer_list:89:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
89 | begin(initializer_list<_Tp> __ils) noexcept
| ^~~~~
/usr/include/c++/9/initializer_list:89:5: note: template argument deduction/substitution failed:
building.cpp:68:24: note: candidate expects 1 argument, 0 provided
68 | while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
| ^
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from building.cpp:1:
/usr/include/c++/9/bits/range_access.h:48:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&)'
48 | begin(_Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/9/bits/range_access.h:48:5: note: template argument deduction/substitution failed:
building.cpp:68:24: note: candidate expects 1 argument, 0 provided
68 | while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
| ^
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,