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$.


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

3 人解决,5 人已尝试。

3 份提交通过,共有 15 份提交。

8.5 EMB 奖励。

创建: 10 年,2 月前.

修改: 3 年,11 月前.

最后提交: 9 月,3 周前.

来源: Southwestern Europe 2002