Submission #796877

#	Time	Username	Problem	Language	Result	Execution time	Memory
796877		resting	Meetings (IOI18_meetings)	C++17	Compilation error	0 ms	0 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int n, q;
struct segtree {
    int l, r, v = 0;
    segtree* lc, * rc;
    segtree* getmem();
    segtree() : segtree(-1, -1) {};
    segtree(int l, int r) : l(l), r(r) {
        if (l == r) return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m + 1, r);
    }
    void upd(int qi, int qv) {
        if (r < qi || l > qi) return;
        if (l == r) { v = qv; return; }
        lc->upd(qi, qv); rc->upd(qi, qv);
        v = max(lc->v, rc->v);
    }
    int q(int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (ql <= l && r <= qr) return v;
        return max(lc->q(ql, qr), rc->q(ql, qr));
    }
};
segtree mem[1000005];
int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }

vector<ll> helper(vector<int> h, vector<int> l, vector<int> r) {
    vector<vector<pair<int, int>>> qq(n);
    for (int i = 0; i < q; i++) qq[r[i]].push_back({ l[i], i });
    vector<ll> c(q);
    ll curad = 0;
    set <pair<int, pair<ll, ll>>> s; //position, {const, slope}
    vector<pair<int, pair<ll, ll>>> st; // index, {value, height} 
    vector<vector<int>> overtake(n + 1);

    auto find_overtake = [&](pair<ll, ll> a, pair<ll, ll>b) { // when a overtakes b as smallest iykyk
        assert(b.second >= a.second); // or its the other way around
        if (a.first <= b.first && a.second <= b.second) return 0;
        if (b.first >= a.first && b.second >= a.second) return n;
        //first i when b.first + b.second * i > a.first + a.second * i
        // (b.second - a.second) * i > a.first - b.first
        // i > (a.first - b.first) / a.second - b.second
        int div = b.second - a.second;
        return (a.first - b.first + (div - 1)) / div;
        };


    segtree ac(n);
    for (int i = 0; i < n; i++) {
        ac.upd(i, h[i]);
        while (st.size() && st.back().second.second <= h[i]) st.pop_back();
        curad = st.back().second.first + (i - st.back().first) * h[i];
        st.push_back({ i, {curad, h[i]} });

        //merge set
        ll mn = curad - h[i] * i, mni = i;
        while (s.size() && prev(s.end())->second.second <= h[i]) {
            ll t = prev(s.end())->second.first + prev(s.end())->second.second * i;
            if (t < mn) {
                mn = t + prev(s.end())->second.second * i - h[i] * (i - 1); mni = prev(s.end())->first;
            }
            s.erase(s.begin());
        }
        s.insert({ mni, {mn, h[i]} });
        if (s.size() > 1) {
            overtake[max(i, find_overtake(prev(s.end())->second, prev(prev(s.end()))->second))].push_back(prev(s.end())->first);
        }

        for (int k = 0; k < overtake[i].size(); k++) {
            auto& x = overtake[i][k];
            auto t = s.lower_bound({ x.first, {0, 0} });
            if (t == s.begin() || t == s.end() || t->second != x.first) continue;
            auto p = prev(t);
            if (p->second.first + p->second.second * i < t->second.first + t->second.second * i) continue;
            s.erase(p);
            if (t == s.begin()) continue;
            auto pp = prev(t);
            overtake[max(i, find_overtake(t->second, pp->second))].push_back(t->first);
        }

        for (auto& x : qq[i]) {
            c[x.second] = 1e18;
            int l = x.first;
            auto owo = lower_bound(st.begin(), st.end(), pair<int, pair<int, int>>({ l, {0, 0} }));
            auto lll = s.lower_bound({ owo->first, {0, 0} });
            if (lll == st.end()) continue;
            c[x.second] = lll->second.first + lll->second.second * i - owo->second.first + (owo->first - l + 1) * h[ll];
        }
    }
}

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> t) {
    n = H.size(); q = L.size();
    vector<ll> a = helper(h, l, r);
    reverse(h.begin(), h.end()); for (int i = 0; i < q; i++) { swap(l[i], r[i]); l[i] = n - 1 - l[i]; r[i] = n - 1 - r[i]; }
    vector<ll> b = helper(h, l, r);
    vector<ll> c(q); for (int i = 0; i < q;i++) c[i] = min(a[i], b[i]);
    return c;
}

Compilation message (stderr)

meetings.cpp: In lambda function:
meetings.cpp:52:48: error: inconsistent types 'int' and 'long long int' deduced for lambda return type
   52 |         return (a.first - b.first + (div - 1)) / div;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
meetings.cpp: In function 'std::vector<long long int> helper(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:56:17: error: no matching function for call to 'segtree::segtree(int&)'
   56 |     segtree ac(n);
      |                 ^
meetings.cpp:13:5: note: candidate: 'segtree::segtree(int, int)'
   13 |     segtree(int l, int r) : l(l), r(r) {
      |     ^~~~~~~
meetings.cpp:13:5: note:   candidate expects 2 arguments, 1 provided
meetings.cpp:12:5: note: candidate: 'segtree::segtree()'
   12 |     segtree() : segtree(-1, -1) {};
      |     ^~~~~~~
meetings.cpp:12:5: note:   candidate expects 0 arguments, 1 provided
meetings.cpp:8:8: note: candidate: 'constexpr segtree::segtree(const segtree&)'
    8 | struct segtree {
      |        ^~~~~~~
meetings.cpp:8:8: note:   no known conversion for argument 1 from 'int' to 'const segtree&'
meetings.cpp:8:8: note: candidate: 'constexpr segtree::segtree(segtree&&)'
meetings.cpp:8:8: note:   no known conversion for argument 1 from 'int' to 'segtree&&'
meetings.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int k = 0; k < overtake[i].size(); k++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
meetings.cpp:79:40: error: request for member 'first' in 'x', which is of non-class type 'int'
   79 |             auto t = s.lower_bound({ x.first, {0, 0} });
      |                                        ^~~~~
meetings.cpp:79:55: error: no matching function for call to 'std::set<std::pair<int, std::pair<long long int, long long int> > >::lower_bound(<brace-enclosed initializer list>)'
   79 |             auto t = s.lower_bound({ x.first, {0, 0} });
      |                                                       ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from meetings.cpp:2:
/usr/include/c++/10/bits/stl_set.h:829:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<int, std::pair<long long int, long long int> >; _Compare = std::less<std::pair<int, std::pair<long long int, long long int> > >; _Alloc = std::allocator<std::pair<int, std::pair<long long int, long long int> > >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, std::pair<long long int, long long int> >, std::pair<int, std::pair<long long int, long long int> >, std::_Identity<std::pair<int, std::pair<long long int, long long int> > >, std::less<std::pair<int, std::pair<long long int, long long int> > >, std::allocator<std::pair<int, std::pair<long long int, long long int> > > >::const_iterator; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<int, std::pair<long long int, long long int> >]'
  829 |       lower_bound(const key_type& __x)
      |       ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:829:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<int, std::pair<long long int, long long int> >&'}
  829 |       lower_bound(const key_type& __x)
      |                   ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:833:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::const_iterator std::set<_Key, _Compare, _Alloc>::lower_bound(const key_type&) const [with _Key = std::pair<int, std::pair<long long int, long long int> >; _Compare = std::less<std::pair<int, std::pair<long long int, long long int> > >; _Alloc = std::allocator<std::pair<int, std::pair<long long int, long long int> > >; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<int, std::pair<long long int, long long int> >, std::pair<int, std::pair<long long int, long long int> >, std::_Identity<std::pair<int, std::pair<long long int, long long int> > >, std::less<std::pair<int, std::pair<long long int, long long int> > >, std::allocator<std::pair<int, std::pair<long long int, long long int> > > >::const_iterator; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<int, std::pair<long long int, long long int> >]'
  833 |       lower_bound(const key_type& __x) const
      |       ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:833:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<int, std::pair<long long int, long long int> >&'}
  833 |       lower_bound(const key_type& __x) const
      |                   ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:839:2: note: candidate: 'template<class _Kt> decltype ((std::set<_Key, _Compare, _Alloc>::iterator)(((std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_lower_bound_tr(__x))) std::set<_Key, _Compare, _Alloc>::lower_bound(const _Kt&) [with _Kt = _Kt; _Key = std::pair<int, std::pair<long long int, long long int> >; _Compare = std::less<std::pair<int, std::pair<long long int, long long int> > >; _Alloc = std::allocator<std::pair<int, std::pair<long long int, long long int> > >]'
  839 |  lower_bound(const _Kt& __x)
      |  ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:839:2: note:   template argument deduction/substitution failed:
meetings.cpp:79:55: note:   couldn't deduce template parameter '_Kt'
   79 |             auto t = s.lower_bound({ x.first, {0, 0} });
      |                                                       ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from meetings.cpp:2:
/usr/include/c++/10/bits/stl_set.h:845:2: note: candidate: 'template<class _Kt> decltype ((std::set<_Key, _Compare, _Alloc>::const_iterator)(((const std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_lower_bound_tr(__x))) std::set<_Key, _Compare, _Alloc>::lower_bound(const _Kt&) const [with _Kt = _Kt; _Key = std::pair<int, std::pair<long long int, long long int> >; _Compare = std::less<std::pair<int, std::pair<long long int, long long int> > >; _Alloc = std::allocator<std::pair<int, std::pair<long long int, long long int> > >]'
  845 |  lower_bound(const _Kt& __x) const
      |  ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:845:2: note:   template argument deduction/substitution failed:
meetings.cpp:79:55: note:   couldn't deduce template parameter '_Kt'
   79 |             auto t = s.lower_bound({ x.first, {0, 0} });
      |                                                       ^
meetings.cpp:80:66: error: request for member 'first' in 'x', which is of non-class type 'int'
   80 |             if (t == s.begin() || t == s.end() || t->second != x.first) continue;
      |                                                                  ^~~~~
meetings.cpp:94:21: error: no match for 'operator==' (operand types are 'std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::iterator')
   94 |             if (lll == st.end()) continue;
      |                 ~~~ ^~ ~~~~~~~~
      |                 |            |
      |                 |            std::vector<std::pair<int, std::pair<long long int, long long int> > >::iterator
      |                 std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from meetings.cpp:2:
/usr/include/c++/10/bits/regex.h:1035:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
 1035 |     operator==(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1035:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from meetings.cpp:2:
/usr/include/c++/10/bits/regex.h:1131:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
 1131 |     operator==(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1131:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from meetings.cpp:2:
/usr/include/c++/10/bits/regex.h:1206:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1206 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1206:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from meetings.cpp:2:
/usr/include/c++/10/bits/regex.h:1298:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
 1298 |     operator==(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1298:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::vector<std::pair<int, std::pair<long long int, long long int> > >::iterator' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from meetings.cpp:2:
/usr/include/c++/10/bits/regex.h:1373:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1373 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1373:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from meetings.cpp:2:
/usr/include/c++/10/bits/regex.h:1466:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
 1466 |     operator==(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1466:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::vector<std::pair<int, std::pair<long long int, long long int> > >::iterator' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from meetings.cpp:2:
/usr/include/c++/10/bits/regex.h:1545:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1545 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1545:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from meetings.cpp:2:
/usr/include/c++/10/bits/regex.h:2101:5: note: candidate: 'template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator==(const std::__cxx11::match_results<_BiIter, _Alloc>&, const std::__cxx11::match_results<_BiIter, _Alloc>&)'
 2101 |     operator==(const match_results<_Bi_iter, _Alloc>& __m1,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:2101:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >' is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from meetings.h:3,
                 from meetings.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:466:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator==(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  466 |     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:466:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >' is not derived from 'const std::pair<_T1, _T2>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from meetings.h:3,
                 from meetings.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:360:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  360 |     operator==(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:360:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >' is not derived from 'const std::reverse_iterator<_Iterator>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from meetings.h:3,
                 from meetings.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:398:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  398 |     operator==(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:398:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >' is not derived from 'const std::reverse_iterator<_Iterator>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from meetings.h:3,
                 from meetings.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1427:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1427 |     operator==(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1427:5: note:   template argument deduction/substitution failed:
meetings.cpp:94:31: note:   'std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >' is not derived from 'const std::move_iterator<_IteratorL>'
   94 |             if (lll == st.end()) continue;
      |                               ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from meetings.h:3,
                 from meetings.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1495:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
 1495 |     operator==(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/i