Problem #2919 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

You are given $n$ closed, integer intervals $[a_{i}, b_{i}]$ and $n$ integers $c_{1}, \dots, c_{n}$ .

Write a program that:

reads the number of intervals, their end points and integers $c_{1}, \dots, 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, \dots, 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 \leq a_{i} \leq b_{i} \leq 50 000$ and $1 \leq c_{i} \leq b_{i} - a_{i} + 1$ .

输出格式

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

样例

Input

Output

3 人解决，5 人已尝试。

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

8.5 EMB 奖励。

创建: 13 年，8 月前.

修改: 7 年，5 月前.

最后提交: 4 年，4 月前.

来源: Southwestern Europe 2002

data structure

2919. Intervals

输入格式

输出格式

样例

服务

开源

关于我们