BOJ 2836 수상 택시

1 개요

BOJ 2836 수상 택시

• 백준 온라인 저지 2836번 문제
• BOJ 46단계

2 C++

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

#define ll long long
#define PAIR pair<int, int>

int N, M;
vector<PAIR> v;

bool cmp(PAIR a, PAIR b) {
    if (a.second == b.second) return a.first > b.first;
    return a.second < b.second;
}

void solve() {
    sort(v.begin(), v.end(), cmp);
    ll res = M;
    PAIR pos = make_pair(1e9, 1e9);
    for (int i = v.size() - 1; i >= 0; i--) {
        if (pos.first <= v[i].first && v[i].second <= pos.second) continue;
        if (v[i].first < pos.first && pos.first <= v[i].second) {
            pos.first = v[i].first;
        } else {
            res += (pos.second - pos.first) * 2;
            pos = v[i];
        }
    }
    res += (pos.second - pos.first) * 2;
    cout << res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        if (a > b) v.push_back({b, a});
    }
    solve();
}