Intervals
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 24099 | Accepted: 9159 |
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 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.
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.
Input
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.
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.
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.
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
#include <iostream>
#include <cstdio>
#include <cstring>
#define inf 0x7ffffff
using namespace std;
const int maxn=;
const int maxm=;
int cnt,fir[maxn],to[maxm],val[maxm],nxt[maxm],dis[maxn],vis[maxn];
void addedge(int a,int b,int v)
{
nxt[++cnt]=fir[a];
to[cnt]=b;
val[cnt]=v;
fir[a]=cnt;
}
int q[maxm],front,back;
void Spfa(int S,int T)
{
fill(dis,dis+S+,inf);
q[front=]=S;back=;
vis[S]=;
dis[S]=;
while(front<back)
{
int node=q[front++];vis[node]=false;
for(int i=fir[node];i;i=nxt[i]){
if(dis[to[i]]<=dis[node]+val[i])continue;
dis[to[i]]=dis[node]+val[i];
if(!vis[to[i]])
q[back++]=to[i];
vis[to[i]]=true;
}
}
} int main()
{
int n,maxl=;
while(~scanf("%d",&n)){
memset(fir,,sizeof(fir));
cnt=;maxl=;
for(int i=;i<=n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
addedge(b,a-,-c);
maxl=max(maxl,b);
}
for(int i=;i<=maxl;i++){
addedge(i-,i,);
addedge(i,i-,);
}
Spfa(maxl,);
printf("%d\n",-dis[]);
}
}