#P18303. Flats

Flats

Flats

矮人们打算把砖块扔进一条笔直、足够深且足够长的沟渠,用砖块围出的空间作为住宅。

沟渠宽度固定。每块砖的宽度都等于沟渠宽度,长度和高度可以不同。因此,可以把整个过程看成一个二维平面上的矩形下落问题。沟底初始是一条水平直线。

按给定顺序,依次把每块砖放在指定的水平区间上方,使它保持水平并竖直下落,直到它的底面碰到沟底或先前落下的砖块。砖块下落过程中及停下后都不会改变朝向。

仅边缘相接或侧面相贴不会阻止砖块下落,侧面可以沿先前砖块的侧面滑动。例如,两个水平区间只有端点相同,不能据此认为后者会落到前者上面。

全部砖块落下后,每个被砖块与沟底完全围住、面积大于零的空白连通区域算作一间住宅。两块空白区域如果只能通过一个点接触,则属于不同住宅:矮人无法穿过宽度为零的通道。

求最终形成的住宅数量。

原题样例中的砖块与住宅,灰色部分为两间住宅

上图展示下面样例的最终状态。图中灰色部分是计入答案的两间住宅。

输入格式

第一行包含一个整数 NN,表示砖块数量。

接下来 NN 行按下落顺序描述砖块。每行包含三个整数 li,ri,hil_i,r_i,h_i,分别表示砖块的左边缘横坐标、右边缘横坐标和高度。砖块的长度为 ri−lir_i-l_i。

数据范围:

  • 1≤N≤2000001\le N\le200000;
  • 0≤li<ri≤2000000\le l_i<r_i\le200000;
  • 1≤hi≤1091\le h_i\le10^9。

输入只有一组数据,没有测试组数 TT。沟渠足够深、足够长,所有砖块都能容纳,且不会碰到沟渠两端。

输出格式

输出一个非负整数,表示全部砖块落下后形成的住宅数量。

样例

4
1 3 2
4 7 2
0 8 1
8 9 2
2