UOJ Logo

NOI.AC

1S 512MB

#742. lecture

Statistics

Lecture

TL : 1s

ML:512MB

题目描述

mas偷偷溜进了讲座的后台,当他发现讲堂如此之大的时候,mas被震惊到了(讲堂的座位可以看成$10^9\times 10^9$的方阵,坐标$(x,y)$,表示第$x$行第$y$个)。

他发现好多人都在玩手机,玩手机的人可以被视为低着头的,而好好听讲的人可以被视为抬着头的。

但是mas发现,由于讲台座位安排的不合理,导致有的抬头听讲的人,会被前面的人挡住,对于位置在$(x,y)$的人,如果$(x-1,y),(x-1,y-1),(x-1,y+1)$这三个位置,都是被挡住的人/抬着头的人,那么这个人就会被挡住。

特殊的,如果$(x-1,y),(x-1,y-1),(x-1,y+1)$三个位置中有一个是不存在的,那么$(x,y)$一定不会被挡住。

注意,无论有没有低头,这个人都有可能被挡住

现在mas统计出,一共有$n$组在认真听讲的人,第$i$组形如$(x_i,l_i,r_i)$表示第$x_i$行第$l_i$到$r_i$个人是在认真听讲的,保证每个人至多在一组里面。

现在mas想知道有多少认真听讲的人被挡住了?

输入

第一行一个整数$n$,表示认真听讲的人的组数。

接下来$n$行,每行三个整数$x_i,l_i,r_i$,描述一组认真听讲的人。

输出

一行一个整数,表示有多少个认真听讲的人被挡住了。

样例输入1

10

5 3 7

3 4 4

3 9 9

7 3 5

8 2 3

7 9 9

8 8 8

3 8 8

3 1 1

3 6 6

样例输出1

1

样例解释

样例中(6,4),(6,5),(6,6),(7,5),(8,4),(9,3)都是被挡住的,其中(7,5)是抬头的,故答案是1

数据范围

保证所有数据中$n\le 10^5,1\le x_i\le 10^9,1\le l_i\le r_i\le 10^9$

  1. (30pts) $x_i,l_i,r_i\le 1000$
  2. (30pts) $n\le 2\times 10^3$
  3. (40pts) 没有特殊限制