2919. Intervals

单点时限: 2.0 sec

内存限制: 256 MB

You are given $n$ closed, integer intervals $[a_i, b_i]$ and $n$ integers $c_1, \ldots, c_n$.

Write a program that:

  • reads the number of intervals, their end points and integers $c_1, \ldots, c_n$ from the standard input,
  • computes the minimal size of a set $\mathscr{Z}$ of integers which has at least $c_i$ common elements with interval $[a_i, b_i]$, for each $i=1,2,\ldots,n$,
  • writes the answer to the standard output.

输入格式

The first line of the input contains an integer $n$ $(1 \leq n \leq 50~000)$ – 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 50~000$ and $1 \le c_i \le b_i - a_i+1$.

输出格式

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

样例

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

2 人解决,4 人已尝试。

2 份提交通过,共有 7 份提交。

9.1 EMB 奖励。

创建: 9 年前.

修改: 2 年,10 月前.

最后提交: 2 年,4 月前.

来源: Southwestern Europe 2002

题目标签