Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 3559    Accepted Submission(s): 1303

Problem Description

You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.



Write a program that:



> reads the number of intervals, their endpoints 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

 

Input

The first line of the input contains an integer n (1 <= n <= 50 000) - 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 <= 50 000 and 1 <= ci <= bi - ai + 1.



Process to the end of file.

 

Output

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.

 

Sample Input

5

3 7 3

8 10 3

6 8 1

1 3 1

10 11 1

 

Sample Output

6

 

Author

1384

 

Recommend

Eddy   |   We have carefully selected several similar problems for you:  1529 1531 1548 1534 1317 

#include<stdio.h>

#include<string.h>

#include<queue>

#include<iostream>

#include<algorithm>

using namespace std;

#define INF 0x3f3f3f

int head[100100],vis[1000100],n,cnt;

int dis[100100];

int l,r;

struct node

{

	int u,v,val;

	int next;

}edge[1001000];

void init()

{

	cnt=0;

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

	l=INF;

	r=-1;

}

void add(int u,int v,int val)

{

	node E={u,v,val,head[u]};

	edge[cnt]=E;

	head[u]=cnt++;

}

void getmap()

{

	int a,b,c;

	for(int i=0;i<n;i++)

	{

		cin>>a>>b>>c;

		l=min(a,l);

		r=max(r,b);

		add(b,a-1,-c);

	}

	for(int i=l;i<=r;i++)

	{

		add(i,i-1,0);

		add(i-1,i,1);

	}

}

void SPFA()

{

	for(int i=l-1;i<=r;i++)

	dis[i]=i==r?0:INF;

	memset(vis,0,sizeof(vis));

	queue<int>q;

	q.push(r);

	vis[r]=1;

	while(!q.empty())

	{

		int u=q.front();

		q.pop();

		vis[u]=0;

		for(int i=head[u];i!=-1;i=edge[i].next)

		{

			node E=edge[i];

			if(dis[E.v]>dis[E.u]+edge[i].val)

			{

				dis[E.v]=dis[E.u]+edge[i].val;

				if(!vis[E.v])

				{

					vis[E.v]=1;

					q.push(E.v);

				}

			}

		}

	}

	cout<<-dis[l-1]<<endl;

}

int main()

{

	while(scanf("%d",&n)!=EOF)

	{

		init();

		getmap();

		SPFA();

	}

	return 0;

}