| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 956868 | Trisanu_Das | Building Bridges (CEOI17_building) | 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 <bits/stdc++.h>
using namespace std;
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 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 l.k * x + l.m;
}
};
int main(){
int n; cin >> n;
int h[n + 2], w[n + 2], dp[n + 1];
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = 1; i <= n; i++) cin >> w[i];
LineContainer hull;
dp[1] = -w[i];
for(int i = 2; i <= n; i++){
hull.add(2 * h[i - 1], h[i - 1] * h[i - 1] + dp[i - 1]);
dp[i] = hull.query(h[i]) + h[i] * h[i] - w[i];
}
cout << dp[n] + accumulate(w + 1, w + n + 1) << '\n';
}
Compilation message (stderr)
building.cpp:5:10: error: 'll' does not name a type
5 | mutable ll k, m, p;
| ^~
building.cpp:7:17: error: 'll' has not been declared
7 | bool operator<(ll x) const { return p < x; }
| ^~
building.cpp: In member function 'bool Line::operator<(const Line&) const':
building.cpp:6:47: error: 'k' was not declared in this scope
6 | bool operator<(const Line& o) const { return k < o.k; }
| ^
building.cpp:6:53: error: 'const struct Line' has no member named 'k'
6 | bool operator<(const Line& o) const { return k < o.k; }
| ^
building.cpp: In member function 'bool Line::operator<(int) const':
building.cpp:7:38: error: 'p' was not declared in this scope
7 | bool operator<(ll x) const { return p < x; }
| ^
building.cpp: At global scope:
building.cpp:12:15: error: 'll' does not name a type
12 | static const ll inf = LLONG_MAX;
| ^~
building.cpp:13:2: error: 'll' does not name a type
13 | ll div(ll a, ll b) { // floored division
| ^~
building.cpp:21:11: error: 'll' has not been declared
21 | void add(ll k, ll m) {
| ^~
building.cpp:21:17: error: 'll' has not been declared
21 | void add(ll k, ll m) {
| ^~
building.cpp:28:2: error: 'll' does not name a type
28 | ll query(ll x) {
| ^~
building.cpp: In member function 'bool LineContainer::isect(std::multiset<Line, std::less<void> >::iterator, std::multiset<Line, std::less<void> >::iterator)':
building.cpp:16:29: error: 'const struct Line' has no member named 'p'
16 | if (y == end()) return x->p = inf, 0;
| ^
building.cpp:16:33: error: 'inf' was not declared in this scope; did you mean 'ynf'?
16 | if (y == end()) return x->p = inf, 0;
| ^~~
| ynf
building.cpp:17:10: error: 'const struct Line' has no member named 'k'
17 | if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
| ^
building.cpp:17:18: error: 'const struct Line' has no member named 'k'
17 | if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
| ^
building.cpp:17:24: error: 'const struct Line' has no member named 'p'
17 | if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
| ^
building.cpp:17:31: error: 'const struct Line' has no member named 'm'
17 | if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
| ^
building.cpp:17:38: error: 'const struct Line' has no member named 'm'
17 | if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
| ^
building.cpp:17:42: error: 'inf' was not declared in this scope; did you mean 'ynf'?
17 | if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
| ^~~
| ynf
building.cpp:18:11: error: 'const struct Line' has no member named 'p'
18 | else x->p = div(y->m - x->m, x->k - y->k);
| ^
building.cpp:18:22: error: 'const struct Line' has no member named 'm'
18 | else x->p = div(y->m - x->m, x->k - y->k);
| ^
building.cpp:18:29: error: 'const struct Line' has no member named 'm'
18 | else x->p = div(y->m - x->m, x->k - y->k);
| ^
building.cpp:18:35: error: 'const struct Line' has no member named 'k'
18 | else x->p = div(y->m - x->m, x->k - y->k);
| ^
building.cpp:18:42: error: 'const struct Line' has no member named 'k'
18 | else x->p = div(y->m - x->m, x->k - y->k);
| ^
building.cpp:19:13: error: 'const struct Line' has no member named 'p'
19 | return x->p >= y->p;
| ^
building.cpp:19:21: error: 'const struct Line' has no member named 'p'
19 | return x->p >= y->p;
| ^
building.cpp: In member function 'void LineContainer::add(int, int)':
building.cpp:22:28: error: no matching function for call to 'LineContainer::insert(<brace-enclosed initializer list>)'
22 | auto z = insert({k, m, 0}), y = z++, x = y;
| ^
In file included from /usr/include/c++/10/set:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
from building.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:502:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = Line]'
502 | insert(const value_type& __x)
| ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:502:32: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const Line&'}
502 | insert(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:507:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = Line]'
507 | insert(value_type&& __x)
| ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:507:27: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::multiset<Line, std::less<void> >::value_type&&' {aka 'Line&&'}
507 | insert(value_type&& __x)
| ~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:532:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, const value_type&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = Line]'
532 | insert(const_iterator __position, const value_type& __x)
| ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:532:7: note: candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_multiset.h:537:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = Line]'
537 | insert(const_iterator __position, value_type&& __x)
| ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:537:7: note: candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_multiset.h:551:2: note: candidate: 'template<class _InputIterator> void std::multiset<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>]'
551 | insert(_InputIterator __first, _InputIterator __last)
| ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:551:2: note: template argument deduction/substitution failed:
building.cpp:22:28: note: candidate expects 2 arguments, 1 provided
22 | auto z = insert({k, m, 0}), y = z++, x = y;
| ^
In file included from /usr/include/c++/10/set:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
from building.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:563:7: note: candidate: 'void std::multiset<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>]'
563 | insert(initializer_list<value_type> __l)
| ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:563:43: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::initializer_list<Line>'
563 | insert(initializer_list<value_type> __l)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:583:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::node_type&&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::node_type]'
583 | insert(node_type&& __nh)
| ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:583:26: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::multiset<Line, std::less<void> >::node_type&&' {aka 'std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::node_type&&'}
583 | insert(node_type&& __nh)
| ~~~~~~~~~~~~^~~~
/usr/include/c++/10/bits/stl_multiset.h:588:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, std::multiset<_Key, _Compare, _Alloc>::node_type&&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::node_type]'
588 | insert(const_iterator __hint, node_type&& __nh)
| ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:588:7: note: candidate expects 2 arguments, 1 provided
building.cpp:23:16: error: 'y' was not declared in this scope; did you mean 'yn'?
23 | while (isect(y, z)) z = erase(z);
| ^
| yn
building.cpp:24:7: error: 'x' was not declared in this scope
24 | if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^
building.cpp:24:34: error: 'y' was not declared in this scope; did you mean 'yn'?
24 | if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
| ^
| yn
building.cpp:25:11: error: 'y' was not declared in this scope; did you mean 'yn'?
25 | while ((y = x) != begin() && (--x)->p >= y->p)
| ^
| yn
building.cpp:25:15: error: 'x' was not declared in this scope
25 | while ((y = x) != begin() && (--x)->p >= y->p)
| ^
building.cpp: In function 'int main()':
building.cpp:41:14: error: 'i' was not declared in this scope
41 | dp[1] = -w[i];
| ^
building.cpp:44:18: error: 'struct LineContainer' has no member named 'query'
44 | dp[i] = hull.query(h[i]) + h[i] * h[i] - w[i];
| ^~~~~
building.cpp:46:46: error: no matching function for call to 'accumulate(int*, int*)'
46 | cout << dp[n] + accumulate(w + 1, w + n + 1) << '\n';
| ^
In file included from /usr/include/c++/10/numeric:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:84,
from building.cpp:1:
/usr/include/c++/10/bits/stl_numeric.h:134:5: note: candidate: 'template<class _InputIterator, class _Tp> _Tp std::accumulate(_InputIterator, _InputIterator, _Tp)'
134 | accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
| ^~~~~~~~~~
/usr/include/c++/10/bits/stl_numeric.h:134:5: note: template argument deduction/substitution failed:
building.cpp:46:46: note: candidate expects 3 arguments, 2 provided
46 | cout << dp[n] + accumulate(w + 1, w + n + 1) << '\n';
| ^
In file included from /usr/include/c++/10/numeric:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:84,
from building.cpp:1:
/usr/include/c++/10/bits/stl_numeric.h:161:5: note: candidate: 'template<class _InputIterator, class _Tp, class _BinaryOperation> _Tp std::accumulate(_InputIterator, _InputIterator, _Tp, _BinaryOperation)'
161 | accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
| ^~~~~~~~~~
/usr/include/c++/10/bits/stl_numeric.h:161:5: note: template argument deduction/substitution failed:
building.cpp:46:46: note: candidate expects 4 arguments, 2 provided
46 | cout << dp[n] + accumulate(w + 1, w + n + 1) << '\n';
| ^