Bò qua đường

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ con bò đang đi qua một con đường. Con đường nằm giữa $y = 0$ và $y = 1$ . Bò $i$ đi từ điểm $(a_{i}, 0)$ đến điểm $(b_{i}, 1)$ .

Hai bò $i$ và $j$ gọi là giao nhau nếu đường đi của chúng cắt nhau (điều này xảy ra khi và chỉ khi $(a_{i} < a_{j}$ và $b_{i} > b_{j})$ hoặc $(a_{i} > a_{j}$ và $b_{i} < b_{j})$ ).

Một con bò gọi là an toàn nếu đường đi của nó không giao với đường đi của bất kỳ con bò nào khác.

Hãy đếm số con bò an toàn.

Dữ liệu vào

Dòng 1: Số nguyên $N$
Dòng $i + 1$ (với $1 \leq i \leq N$ ): Hai số nguyên $a_{i}$ và $b_{i}$

Dữ liệu ra

Một số nguyên duy nhất: số con bò an toàn

Ràng buộc

$1 \leq N \leq 100000$
$- 10^{6} \leq a_{i}, b_{i} \leq 10^{6}$
Tất cả $a_{i}$ phân biệt, tất cả $b_{i}$ phân biệt

Ví dụ

Input	Output	Giải thích
4 -3 4 7 8 10 16 3 9	2	Bò 1 ( $a = - 3, b = 4$ ) và bò 3 ( $a = 10, b = 16$ ) an toàn. Bò 2 và bò 4 giao nhau nhau.
10 7 9 -1 1 -8 -9 13 20 16 18 -2 -8 -5 -7 6 4 14 13 -18 -16	5	Có 5 con bò an toàn.

Bình luận

Không có bình luận tại thời điểm này.