Codeforces Round #422 (Div. 2) C. Hacker, pack your bags!

http://codeforces.com/contest/822/problem/C

n과 k가 주어진다.

n은 비행기 티켓의 개수 이다. 각 티켓에는 l,r,c 세개의 정수가 있고 l은 출국일, r은 입국일, c는 티켓 가격이다.

범위는 l,r <= 2*10^5, c <= 10^9 이다.

각 티켓을 사용했을 때 여행을 할 수 있는 날짜는 r-l+1 일이다.

날이 서로 하루라도 겹치지않는 두 티켓을 사서 정확히 k일간 여행을 가고싶다.

이 때 티켓을 사는 최소 비용을 구하는 문제이다.

두 티켓을 사는 것이기 때문에 티켓을 하나씩 보는데 현재 보는 티켓을 두번째 사는 티켓으로 가정했을 때의

답을 갱신해 나가는 식으로 답을 구할 수가 있다. 그러려면 당연히 첫번째 살 수 있는 티켓들의 후보에 대한 정보를

미리 구해놓고 빠른시간안에 이 정보를 활용하여 답을 갱신할 수 있어야 할 것이다.

그리하여 이 문제는 라인 스위핑으로 풀 수가 있다.

각 티켓의 여행날짜를 하나의 구간으로 보면 각 구간에 대해서 시작일로 벡터에 한번넣고, 끝 일로 벡터에 한번넣는다.

예를 들어 

vector<pair<pair<int,int>,pair<int,int> > > v; 라는 변수를 하나 만들엉서

pair를 <<날짜, 여행기간>, <가격, 끝or시작> > 로 구성한다. 그리고 정렬을 때리고

1. 끝나는 지점일 땐

dp[i] : 지금까지 본 티켓들중 i의 여행기간을 가지는 티켓의 최소 가격.

(지금까지 본 티켓들이라는 말은 구간의 끝나는 지점에 이미 도달했던 티켓이라는 것이다.)

dp 배열을 갱신시켜 준다.

2. 시작하는 지점일 땐

현재 보는 티켓의 사이즈가 s 일때 dp[k-s] 와 현재 보는 티켓의 가격을 더한 값이 현재 보는 티켓을

두번째 사는 티켓으로 할 때의 최소 가격 합이다.

주의해야 할 것은 두 티켓의 날이 서로 하루라도 겹치면 안되기 때문에 서로 시작하는 혹은 끝나는 날짜가

같은 두개 이상의 티켓들이 있을 때에는 구간의 시작부분을 먼저 봐준다. 왜냐하면 끝나는 부분을 먼저보면

끝나는 부분으로 먼저 dp 배열을 갱신하기 때문에 시작부분을 볼 때 그것도 고려하여 답을 계산하기 때문.

// #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
struct ticket{
    int pos,len,cost,isEnd;
    bool operator<(const ticket& rhs) const{
        if(pos == rhs.pos) return isEnd < rhs.isEnd;
        return pos < rhs.pos;
    }
};
int n,k;
vector<ticket> v;
ll dp[200003];
int main() {
    memset(dp,0x3c,sizeof(dp));
    cin >> n >> k;
    for(int i = 0 ; i < n; i++){
        int l,r,c;
        cin >> l >> r >> c;
        v.push_back(ticket{l,r-l+1,c,0});
        v.push_back(ticket{r,r-l+1,c,1});
    }
    sort(v.begin(), v.end());
    ll ans = infl;
    for(int i = 0 ; i < (int)v.size(); i++){
        auto p = v[i];
        if(p.isEnd) dp[p.len] = min(dp[p.len], (ll)p.cost);
        else if(p.len < k) ans = min(ans, dp[k - p.len] + p.cost);
    }
    if(ans == infl) ans = -1;
    cout << ans;
    return 0;
}