Submission #797898

#	Time	Username	Problem	Language	Result	Execution time	Memory
797898		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
#define t prev(s.end())
#define ff first
#define ss second
#define v vector

int n, q;

v<ll> helper(v<int32_t> h, v<int32_t> l, v<int32_t> r) {
    v<v<pair<int, int>>> qq(n);
    for (int i = 0; i < q; i++) qq[r[i]].push_back({ l[i], i });
    v<ll> c(q);
    ll curad = 0;
    set <pair<int, pair<ll, ll>>> s;
    v<pair<int, pair<ll, int>>> st;
    v<v<int>> overtake(n + 1);

    auto find_overtake = [&](pair<ll, ll> a, pair<ll, ll>b) -> int {
        if (a.ff <= b.ff && a.ss <= b.ss) return 0;
        if (b.ff <= a.ff && b.ss <= a.ss) return n;
        int div = b.ss - a.ss;
        return (int)min((ll)n, (a.ff - b.ff + (div - 1)) / div);
    };

    for (int i = 0; i < n; i++) {
        while (st.size() && st.back().ss.ss < h[i]) st.pop_back();
        if (st.size())curad = st.back().ss.ff + (ll)(i - st.back().ff) * h[i];
        else curad = (ll)(i + 1) * h[i];
        st.push_back({ i, {curad, h[i]} });

        ll mn = curad - (ll)h[i] * i;int mni = i;

        while (s.size() && t->ss.ss < h[i]) {
            ll t = t->ss.ff + t->ss.ss * (i - 1) - (ll)h[i] * (i - 1);
            if (t < mn) {
                mn = t; mni = t->ff;
            }
            s.erase(t);
        }
        s.insert({ mni, {mn, h[i]} });
        if (s.size() > 1) {
            overtake[max(i, min(n, find_overtake(t->ss, prev(t)->ss)))].push_back(t->ff);
        }

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


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

    return c;
}

v<ll> minimum_costs(v<int32_t> h, v<int32_t> l, v<int32_t> r) {
    n = h.size(); q = l.size();
    v<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]; }
    v<ll> b = helper(h, l, r);
    v<ll> c(q); for (int i = 0; i < q;i++) c[i] = min(a[i], b[i]);
    for (int i = 0; i < q; i++) {
        if (c[i] == 1e18)
            c[i] = (ll)(r[i] - l[i] + 1) * h[l[i]];
    }
    return c;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> helper(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:6:21: error: cannot convert 'std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator' {aka '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'} to 'long long int' in initialization
    6 | #define t prev(s.end())
      |                ~~~~~^~
      |                     |
      |                     std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator {aka 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}
meetings.cpp:38:16: note: in expansion of macro 't'
   38 |             ll t = t->ss.ff + t->ss.ss * (i - 1) - (ll)h[i] * (i - 1);
      |                ^
meetings.cpp:6:23: error: 'prev' cannot be used as a function
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:39:17: note: in expansion of macro 't'
   39 |             if (t < mn) {
      |                 ^
meetings.cpp:6:23: error: 'prev' cannot be used as a function
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:40:22: note: in expansion of macro 't'
   40 |                 mn = t; mni = t->ff;
      |                      ^
meetings.cpp:6:23: error: 'prev' cannot be used as a function
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:40:31: note: in expansion of macro 't'
   40 |                 mn = t; mni = t->ff;
      |                               ^
meetings.cpp:6:23: error: 'prev' cannot be used as a function
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:42:21: note: in expansion of macro 't'
   42 |             s.erase(t);
      |                     ^
meetings.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int k = 0; k < overtake[i].size(); k++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
meetings.cpp:51:20: error: expected ',' or ';' before '=' token
   51 |             auto t = s.lower_bound({ x, {(ll)-1e18, (ll)-1e18} });
      |                    ^
meetings.cpp:51:65: error: expected primary-expression before ')' token
   51 |             auto t = s.lower_bound({ x, {(ll)-1e18, (ll)-1e18} });
      |                                                                 ^
meetings.cpp:6:23: error: no match for call to '(std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >) (std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator)'
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:52:17: note: in expansion of macro 't'
   52 |             if (t == s.begin() || t == s.end() || t->ff != x) continue;
      |                 ^
meetings.cpp:6:23: error: no match for call to '(std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >) (std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator)'
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:52:35: note: in expansion of macro 't'
   52 |             if (t == s.begin() || t == s.end() || t->ff != x) continue;
      |                                   ^
meetings.cpp:6:23: error: no match for call to '(std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >) (std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator)'
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:52:51: note: in expansion of macro 't'
   52 |             if (t == s.begin() || t == s.end() || t->ff != x) continue;
      |                                                   ^
meetings.cpp:6:23: error: no match for call to '(std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >) (std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator)'
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:53:27: note: in expansion of macro 't'
   53 |             auto p = prev(t);
      |                           ^
meetings.cpp:6:23: error: no match for call to '(std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >) (std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator)'
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:54:43: note: in expansion of macro 't'
   54 |             if (p->ss.ff + p->ss.ss * i < t->ss.ff + t->ss.ss * i) continue;
      |                                           ^
meetings.cpp:6:23: error: no match for call to '(std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >) (std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator)'
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:54:54: note: in expansion of macro 't'
   54 |             if (p->ss.ff + p->ss.ss * i < t->ss.ff + t->ss.ss * i) continue;
      |                                                      ^
meetings.cpp:6:23: error: no match for call to '(std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >) (std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator)'
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:56:17: note: in expansion of macro 't'
   56 |             if (t == s.begin()) continue;
      |                 ^
meetings.cpp:6:23: error: no match for call to '(std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >) (std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator)'
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:57:28: note: in expansion of macro 't'
   57 |             auto pp = prev(t);
      |                            ^
meetings.cpp:6:23: error: no match for call to '(std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >) (std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator)'
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:58:50: note: in expansion of macro 't'
   58 |             overtake[max(i, min(n, find_overtake(t->ss, pp->ss)))].push_back(t->ff);
      |                                                  ^
meetings.cpp:6:23: error: no match for call to '(std::_Rb_tree_const_iterator<std::pair<int, std::pair<long long int, long long int> > >) (std::set<std::pair<int, std::pair<long long int, long long int> > >::iterator)'
    6 | #define t prev(s.end())
      |                       ^
meetings.cpp:58:78: note: in expansion of macro 't'
   58 |             overtake[max(i, min(n, find_overtake(t->ss, pp->ss)))].push_back(t->ff);
      |                                                                              ^