trang chủ / đề bài / cowcross

Bò qua đường

Đề bài

Mô tả

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 (ai,0) đến điểm (bi,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 (ai<aj và bi>bj) hoặc (ai>aj và bi<bj)).

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≤i≤N): Hai số nguyên ai và bi

Dữ liệu ra

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

Ràng buộc

  • 1≤N≤100000
  • −106≤ai,bi≤106
  • Tất cả ai phân biệt, tất cả bi 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.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0