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.
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
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #define inf 0x7ffffff 5 using namespace std; 6 const int maxn=50010; 7 const int maxm=1000010; 8 int cnt,fir[maxn],to[maxm],val[maxm],nxt[maxm],dis[maxn],vis[maxn]; 9 void addedge(int a,int b,int v) 10 { 11 nxt[++cnt]=fir[a]; 12 to[cnt]=b; 13 val[cnt]=v; 14 fir[a]=cnt; 15 } 16 int q[maxm],front,back; 17 void Spfa(int S,int T) 18 { 19 fill(dis,dis+S+1,inf); 20 q[front=1]=S;back=2; 21 vis[S]=1; 22 dis[S]=0; 23 while(front<back) 24 { 25 int node=q[front++];vis[node]=false; 26 for(int i=fir[node];i;i=nxt[i]){ 27 if(dis[to[i]]<=dis[node]+val[i])continue; 28 dis[to[i]]=dis[node]+val[i]; 29 if(!vis[to[i]]) 30 q[back++]=to[i]; 31 vis[to[i]]=true; 32 } 33 } 34 } 35 36 int main() 37 { 38 int n,maxl=0; 39 while(~scanf("%d",&n)){ 40 memset(fir,0,sizeof(fir)); 41 cnt=0;maxl=0; 42 for(int i=1;i<=n;i++){ 43 int a,b,c; 44 scanf("%d%d%d",&a,&b,&c); 45 addedge(b,a-1,-c); 46 maxl=max(maxl,b); 47 } 48 for(int i=1;i<=maxl;i++){ 49 addedge(i-1,i,1); 50 addedge(i,i-1,0); 51 } 52 Spfa(maxl,0); 53 printf("%d ",-dis[0]); 54 } 55 }