Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 27746		Accepted: 10687

You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn. 
Write a program that: 
reads the number of intervals, their end points and integers c1, ..., cn from the standard input, 
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n, 
writes the answer to the standard output. 

The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.

5

3 7 3

8 10 3

6 8 1

1 3 1

10 11 1

6

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<deque>

#include<iomanip>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<functional>

#include<memory>

#include<list>

#include<string>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

//[a,b]区间内至少有c个数在集合内，问集合最少包含多少点

//a,b 可以取0 再读入的时候手动 a++,b++

//定义ti 为[0,i]内至少有多少个数字，那么由ta-1 - tb <= -c

//由ti的定义可以推出它的性质1.ti-ti+1<=0 ti+1-ti<=1

const int MAXM = * + ;

const int MAXN =  + ;

struct edge

{

    LL to, next, dis;

}E[MAXM];

LL head[MAXN],tot;

LL dist[MAXN];

bool vis[MAXN];

void init()

{

    tot = ;

    memset(head, -, sizeof(head));

}

void spfa(LL ed)

{

    memset(dist, 0x3f3f3f3f, sizeof(dist));

    memset(vis, false, sizeof(vis));

    queue<LL> q;

    q.push();

    vis[] = true;

    dist[] = ;

    while (!q.empty())

    {

        LL f = q.front();

        q.pop();

        vis[f] = false;

        for (LL i = head[f]; i != -; i = E[i].next)

        {

            LL v = E[i].to, d = E[i].dis;

            if (dist[v] > dist[f] + d)

            {

                dist[v] = dist[f] + d;

                if (!vis[v])

                {

                    vis[v] = true;

                    q.push(v);

                }

            }

        }

    }

    cout << -dist[ed] << endl;

}

void addedge(LL u, LL v, LL d)

{

    E[tot].to = v;

    E[tot].dis = d;

    E[tot].next = head[u];

    head[u] = tot++;

}

int main()

{

    ios::sync_with_stdio();

    init();

    LL f, t, d, ed;

    LL n;

    cin >> n;

    while (n--)

    {

        cin >> f >> t >> d;

        f++, t++;

        addedge(f - , t, -d);

        ed = max(t, ed);

    }

    for (int i = ; i < ed; i++)

    {

        addedge(i, i + , );

        addedge(i + , i, );

    }

    spfa(ed);

}