## Intervals

### 题目描述

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

### 输入格式

The first line of the input contains an integer $n$ ($1 \le n \le 50000$) -- the number of intervals. The following n lines describe the intervals. The ($i+1$)-th line of the input contains three integers $a_i$, $b_i$ and $c_i$ separated by single spaces and such that $0 \le a_i \le b_i \le 50000$ and $1 \le c_i \le b_i-a_i+1$.

### 输出格式

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

### 样例输入

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1


### 样例输出

6


## 题解

• $s[i]-s[i-1] \ge 0$
$\rightarrow s[i]+0 \ge s[i-1]$
• $s[i]-s[i-1] \le 1$
$\rightarrow s[i-1]+1 \ge s[i]$

$s[i-1]$到$s[i]$长度为$1$的边。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int x,y,c;
struct aa{
int to,nxt,v;
}p[500009];
int h[50009],len;
int mx;
int s[50009];
p[++len].to=v;
p[len].v=w;
p[len].nxt=h[u];
h[u]=len;
}
bool k[50009];
void dfs(int u){
int q[500009],l=0,r=0;
q[0]=u;
while(l!=r+1){
u=q[l];
l++;l%=500000;
k[u]=0;
for(int j=h[u];j;j=p[j].nxt){
if(s[p[j].to]>s[u]+p[j].v){
s[p[j].to]=s[u]+p[j].v;
r++;
r%=500000;//循环队列
if(!k[p[j].to]) q[r]=p[j].to;
k[p[j].to]=1;
}
}
}
}
int main(){
while(scanf("%d",&n)!=EOF){
memset(s,1,sizeof(s));
memset(h,0,sizeof(h));
len=0;
for(int j=1;j<=n;j++){
scanf("%d%d%d",&x,&y,&c);
x++;y++;
mx=max(mx,y);
}