Preparando MOJI

Bicolored Segments

2000ms 262144K

Description:

You are given $$$n$$$ segments $$$[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$$$. Each segment has one of two colors: the $$$i$$$-th segment's color is $$$t_i$$$.

Let's call a pair of segments $$$i$$$ and $$$j$$$ bad if the following two conditions are met:

  • $$$t_i \ne t_j$$$;
  • the segments $$$[l_i, r_i]$$$ and $$$[l_j, r_j]$$$ intersect, embed or touch, i. e. there exists an integer $$$x$$$ such that $$$x \in [l_i, r_i]$$$ and $$$x \in [l_j, r_j]$$$.

Calculate the maximum number of segments that can be selected from the given ones, so that there is no bad pair among the selected ones.

Input:

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — number of segments.

The next $$$n$$$ lines contains three integers $$$l_i, r_i, t_i$$$ ($$$1 \le l_i \le r_i \le 10^9; t_i \in \{1, 2\}$$$) — description of the $$$i$$$-th segment.

Output:

Print the maximum number of segments that can be selected, so that there is no bad pair among the selected segments.

Sample Input:

3
1 3 1
4 6 2
2 5 1

Sample Output:

2

Sample Input:

5
5 8 1
1 3 2
3 4 2
6 6 1
2 10 2

Sample Output:

4

Sample Input:

7
19 20 1
13 15 2
6 11 2
4 10 1
14 17 1
13 13 2
5 9 1

Sample Output:

5

Informação

Codeforces

Provedor Codeforces

Código CF1389F

Tags

data structuresdpgraph matchingssortings

Submetido 0

BOUA! 0

Taxa de BOUA's 0%

Datas 09/05/2023 10:05:10

Relacionados

Nada ainda