Language: C++


#include <iostream>
#include <vector>
#include <set>

using namespace std;

using LR = pair<long, long>;

using OrderedRanges = multiset<LR, function<bool(const LR &, const LR &)>>;

class Ranges {
    OrderedRanges lefts;
    OrderedRanges rights;

public:
    Ranges(const vector<LR> &ranges) :
        lefts(ranges.begin(), ranges.end(),
              [](const LR &lhs, const LR &rhs) {
                  return lhs.first > rhs.first ||
                      lhs.first == rhs.first && lhs.second > rhs.second;
              }),
        rights(ranges.begin(), ranges.end(),
               [](const LR &lhs, const LR &rhs) {
                   return lhs.second < rhs.second ||
                                       lhs.second == rhs.second &&
                                       lhs.first < rhs.first;
        })
    {}

    LR pop(OrderedRanges &take_from, OrderedRanges &other) {
        auto first = take_from.begin();
        LR ret = *first;
        take_from.erase(first);
        other.erase(other.find(ret));
        return ret;
    }

    LR pop(bool left) {
        return left ? pop(lefts, rights) : pop(rights, lefts);
    }

    // friend ostream &operator<<(ostream &os, const Ranges &ranges);
};

// ostream &operator<<(ostream &os, const Ranges &ranges) {
//     os << ranges.lefts << "," << ranges.rights << endl;
//     return os;
// }

long calc(const vector<LR> &ranges, bool left) {
    Ranges world(ranges);
    long current = 0;
    long ret = 0;
    for(long i=0; i<ranges.size(); i++) {
        // cerr << i << ": " << endl;
        LR pair = world.pop(left);
        // cerr << "popped: " << pair << endl;
        // cerr << "world: " << world << endl;
        if(left) {
            if (current < pair.first) {
                ret += pair.first - current;
                current = pair.first;
            }
        } else {
            if (current > pair.second) {
                ret += current - pair.second;
                current = pair.second;
            }
        }
        left = !left;
    }
    ret += abs(current);
    return ret;
}

int main() {
    long N;
    cin >> N;
    vector<LR> ranges;
    for(long i=0; i<N; i++){
        long l, r;
        cin >> l >> r;
        ranges.push_back(make_pair(l, r));
    }

    //cerr << "start calc v1" << endl;
    long v1 = calc(ranges, true);
    long v2 = calc(ranges, false);

    //cerr << "v1:" << v1 << endl;
    //cerr << "v2:" << v2 << endl;

    cout << max(v1, v2) << endl;
}


Compiler output:
a.cc:10:36: error: 'function' was not declared in this scope
   10 | using OrderedRanges = multiset<LR, function<bool(const LR &, const LR &)>>;
      |                                    ^~~~~~~~
a.cc:5:1: note: 'std::function' is defined in header '<functional>'; this is probably fixable by adding '#include <functional>'
    4 | #include <set>
  +++ |+#include <functional>
    5 | 
a.cc:10:72: error: expression list treated as compound expression in functional cast [-fpermissive]
   10 | using OrderedRanges = multiset<LR, function<bool(const LR &, const LR &)>>;
      |                                                                        ^
a.cc:10:73: error: template argument 2 is invalid
   10 | using OrderedRanges = multiset<LR, function<bool(const LR &, const LR &)>>;
      |                                                                         ^~
a.cc:13:5: error: 'OrderedRanges' does not name a type
   13 |     OrderedRanges lefts;
      |     ^~~~~~~~~~~~~
a.cc:14:5: error: 'OrderedRanges' does not name a type
   14 |     OrderedRanges rights;
      |     ^~~~~~~~~~~~~
a.cc:31:12: error: 'OrderedRanges' has not been declared
   31 |     LR pop(OrderedRanges &take_from, OrderedRanges &other) {
      |            ^~~~~~~~~~~~~
a.cc:31:38: error: 'OrderedRanges' has not been declared
   31 |     LR pop(OrderedRanges &take_from, OrderedRanges &other) {
      |                                      ^~~~~~~~~~~~~
a.cc: In constructor 'Ranges::Ranges(const std::vector<std::pair<long int, long int> >&)':
a.cc:18:9: error: class 'Ranges' does not have any field named 'lefts'
   18 |         lefts(ranges.begin(), ranges.end(),
      |         ^~~~~
a.cc:23:9: error: class 'Ranges' does not have any field named 'rights'
   23 |         rights(ranges.begin(), ranges.end(),
      |         ^~~~~~
a.cc: In member function 'LR Ranges::pop(int&, int&)':
a.cc:32:32: error: request for member 'begin' in 'take_from', which is of non-class type 'int'
   32 |         auto first = take_from.begin();
      |                                ^~~~~
a.cc:34:19: error: request for member 'erase' in 'take_from', which is of non-class type 'int'
   34 |         take_from.erase(first);
      |                   ^~~~~
a.cc:35:15: error: request for member 'erase' in 'other', which is of non-class type 'int'
   35 |         other.erase(other.find(ret));
      |               ^~~~~
a.cc:35:27: error: request for member 'find' in 'other', which is of non-class type 'int'
   35 |         other.erase(other.find(ret));
      |                           ^~~~
a.cc: In member function 'LR Ranges::pop(bool)':
a.cc:40:27: error: 'lefts' was not declared in this scope; did you mean 'left'?
   40 |         return left ? pop(lefts, rights) : pop(rights, lefts);
      |                           ^~~~~
      |                           left
a.cc:40:34: error: 'rights' was not declared in this scope
   40 |         return left ? pop(lefts, rights) : pop(rights, lefts);
      |                                  ^~~~~~