Submission #995685

#	Time	Username	Problem	Language	Result	Execution time	Memory
995685		biank	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 KiB

aliens

#include<bits/stdc++.h>

using namespace std;

#define all(x) begin(x),end(x)
#define sz(x) int(x.size())

using ll = long long;
using ld = long double;

struct Line {
	ll m, b, k;
    mutable ld p; //we need to change p in the set
	bool operator<(const Line& o) const { //order by slope
        return m < o.m;
    }
	bool operator<(ld x) const {
        return p < x;
    }
    ld intersectX(const Line l) const {
        return ld(b - l.b) / (l.m - m);
    }
};

struct LineContainer : multiset<Line, less<>> {
	static constexpr ld INF = 1e18;
    bool intersect(iterator x, iterator y) {
        if (y == end()) {
            x->p = INF;
            return false;
        }
        if (x->m == y->m) { //parallel
            if (x->b > y->b) x->p = INF;
            else x->p = -INF;
        } else {
            x->p = x->intersectX(*y);
        }
        return x->p >= y->p;
    }
    void add(ll m, ll b, ll k) {
        auto next = emplace(m, b, k, 0);
        auto prev = next, curr = next;
        next++;
 
        while (intersect(curr, next)) {
            next = erase(next);
        }
        
        if (prev != begin() && intersect(--prev, curr)) {
            curr = erase(curr);
            intersect(prev, curr);
        }
        curr = prev;
        while (curr != begin() && (--prev)->p >= curr->p) {
            curr = erase(curr);
            intersect(prev, curr);
            curr = prev;
        }
    }
	pair<ll, ll> query(ll x) {
		assert(!empty());
		Line l = *lower_bound(x);
		return {l.m * x + l.b, l.k};
	}
};

struct Point {
    ll x, y;
};

ll take_photos(int n, int /*m*/, int k, vector<int> r, vector<int> c){
    vector<Point> v;
    for (int i = 0; i < n; i++) {
        if (r[i] < c[i]) swap(r[i], c[i]);
        v.emplace_back(r[i], c[i]);
    }
    sort(all(v), [](const Point &a, const Point &b) {
        if (a.y != b.y) return a.y < b.y;
        return a.x > b.x;
    });
    vector<Point> p{v[0]};
    for (int i = 1; i < n; i++) {
        if (p.back().x < v[i].x) p.push_back(v[i]);
    }
    n = sz(p);
    k = min(k, n);
    auto sq = [](ll x) { return x * x; };
    auto check = [&](ll lambda) {
        LineContainer dp;
        ll res = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            ll m = -2LL * (p[i].y - 1LL);
            ll b = res + sq(p[i].y - 1LL);
            if (i > 0) b -= sq(max(p[i - 1].x - p[i].y + 1LL, 0LL));
            dp.add(m, b, cnt);
            tie(res, cnt) = dp.query(p[i].x);
            res += sq(p[i].x) + lambda, cnt++;
        }
        return pair<ll, ll>{res, cnt};
    };
    ll lo = 0, hi = 1e13;
    while (hi - lo > 1) {
        ll mid = (hi - lo) / 2 + lo;
        if (check(mid).second <= k) hi = mid;
        else lo = mid;
    }
    return check(hi).first - k * hi;
}

Compilation message (stderr)

In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
                 from /usr/include/c++/10/bits/allocator.h:46,
                 from /usr/include/c++/10/string:41,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from aliens.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = Point; _Args = {int&, int&}; _Tp = Point]':
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(std::allocator_traits<std::allocator<_CharT> >::allocator_type&, _Up*, _Args&& ...) [with _Up = Point; _Args = {int&, int&}; _Tp = Point; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<Point>]'
/usr/include/c++/10/bits/vector.tcc:115:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int&, int&}; _Tp = Point; _Alloc = std::allocator<Point>; std::vector<_Tp, _Alloc>::reference = Point&]'
aliens.cpp:75:34:   required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: new initializer expression list treated as compound expression [-fpermissive]
  150 |  { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'Point::Point(int&)'
aliens.cpp:67:8: note: candidate: 'Point::Point()'
   67 | struct Point {
      |        ^~~~~
aliens.cpp:67:8: note:   candidate expects 0 arguments, 1 provided
aliens.cpp:67:8: note: candidate: 'constexpr Point::Point(const Point&)'
aliens.cpp:67:8: note:   no known conversion for argument 1 from 'int' to 'const Point&'
aliens.cpp:67:8: note: candidate: 'constexpr Point::Point(Point&&)'
aliens.cpp:67:8: note:   no known conversion for argument 1 from 'int' to 'Point&&'
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
                 from /usr/include/c++/10/bits/allocator.h:46,
                 from /usr/include/c++/10/string:41,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from aliens.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = Line; _Args = {long long int&, long long int&, long long int&, int}; _Tp = std::_Rb_tree_node<Line>]':
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(std::allocator_traits<std::allocator<_CharT> >::allocator_type&, _Up*, _Args&& ...) [with _Up = Line; _Args = {long long int&, long long int&, long long int&, int}; _Tp = std::_Rb_tree_node<Line>; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<std::_Rb_tree_node<Line> >]'
/usr/include/c++/10/bits/stl_tree.h:618:32:   required from 'void std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_construct_node(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type, _Args&& ...) [with _Args = {long long int&, long long int&, long long int&, int}; _Key = Line; _Val = Line; _KeyOfValue = std::_Identity<Line>; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<Line>*]'
/usr/include/c++/10/bits/stl_tree.h:635:21:   required from 'std::_Rb_tree_node<_Val>* std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_create_node(_Args&& ...) [with _Args = {long long int&, long long int&, long long int&, int}; _Key = Line; _Val = Line; _KeyOfValue = std::_Identity<Line>; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<Line>*]'
/usr/include/c++/10/bits/stl_tree.h:2440:33:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_emplace_equal(_Args&& ...) [with _Args = {long long int&, long long int&, long long int&, int}; _Key = Line; _Val = Line; _KeyOfValue = std::_Identity<Line>; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::iterator]'
/usr/include/c++/10/bits/stl_multiset.h:458:32:   required from 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::emplace(_Args&& ...) [with _Args = {long long int&, long long int&, long long int&, int}; _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]'
aliens.cpp:41:39:   required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: new initializer expression list treated as compound expression [-fpermissive]
  150 |  { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'Line::Line(int)'
aliens.cpp:11:8: note: candidate: 'Line::Line()'
   11 | struct Line {
      |        ^~~~
aliens.cpp:11:8: note:   candidate expects 0 arguments, 1 provided
aliens.cpp:11:8: note: candidate: 'constexpr Line::Line(const Line&)'
aliens.cpp:11:8: note:   no known conversion for argument 1 from 'int' to 'const Line&'
aliens.cpp:11:8: note: candidate: 'constexpr Line::Line(Line&&)'
aliens.cpp:11:8: note:   no known conversion for argument 1 from 'int' to 'Line&&'