Chương trình giải trí


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 488M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Tài là một người bận rộn nhưng rất thích xem các chương trình giải trí trên TV, do vậy cứ vào cuối tuần cậu thường dành rất nhiều thời gian để xem các chương trình giải trí. Vì tất cả chương trình giải trí luôn thú vị, Tài luôn muốn khi xem một chương trình thì sẽ xem hết hoàn chỉnh từ thời điểm chiếu đến thời điểm kết thúc của chương trình đó.

Nói cách khác, nếu chương trình thứ i có thời điểm bắt đầu là si và thời điểm kết thúc là ti, Tài sẽ xem xem từ mốc thời gian si cho đến ti. Do vậy, Tài muốn biết rằng số cặp chương trình có lịch phát sóng không phù hợp nhau để cân nhắc chọn lựa chương trình để xem.

n chương trình giải trí, chương trình thứ i (1 ≤ i ≤ n) có thời điểm bắt đầu là si và thời điểm kết thúc là ti. Chương trình giải trí thứ i và chương trình giải trí thứ j (1 ≤ i < j ≤ n) được gọi là không phù hợp với nhau về lịch phát sóng nếu Tài không thể xem trọn vẹn nội dung của cả 2 chương trình giải trí này.

Nếu thời điểm kết thúc ti của chương trình i là thời điểm bắt đầu sj của chương trình j thì 2 chương trình này vẫn được xem là có lịch phát sóng phù hợp với nhau. Hãy giúp Tài xác định được số cặp chương trình có lịch phát sóng không phù hợp nhau.

Đầu vào

• Dòng thứ nhất ghi 1 số nguyên dương n (1 ≤ n ≤ 10^6).

• Dòng thứ i trong n dòng tiếp theo chứa 2 số nguyên dương si, ti là thời điểm bắt đầu và kết thúc của chương trình giải trí thứ i (1 ≤ si < ti ≤ 10^6).

Đầu ra

• In ra số cặp chương trình có lịch phát sóng không phù hợp nhau.

Ví dụ:

Đầu vào

3
5 10
4 7
1 5

Đầu ra

2

Giải thích:

Ví dụ 1 có 3 chương trình giải trí như sau:chương trình 1 (s1 = 5, t1 = 10), chương trình 2 (s2 = 4, t2 = 7), và chương trình 3 (s3 = 1, t3 = 5). Chương trình 1 và chương 3 có lịch phát sóng phù hợp nhau. Trong khi đó, các cặp chương trình (1, 2) và (2, 3) có lịch phát sóng không phù hợp nhau.


Comments

There are no comments at the moment.