trang chủ / đề bài / hillwalk

Đi Trên Đồi

Đề bài

Mô tả

Có N đoạn dốc, mỗi đoạn là một đoạn thẳng từ điểm (x1,y1) đến (x2,y2) với x1<x2 và y1<y2 (dốc đi lên từ trái sang phải). Không có hai đoạn dốc nào chạm nhau, kể cả tại đầu mút.

Bạn bắt đầu tại (0,0), điểm này được đảm bảo là đầu trái của đúng một đoạn dốc (đoạn đó không nhất thiết được cho đầu tiên trong dữ liệu vào). Bạn đi theo hướng tăng x. Khi đến đầu phải (x2,y2) của đoạn dốc đang đứng, bạn rơi thẳng xuống theo phương thẳng đứng. Nếu có đoạn dốc khác chứa hoành độ x2 theo nghĩa x1′≤x2<x2′ (đầu trái đóng, đầu phải mở) và có độ cao tại x2 nhỏ hơn y2, bạn rơi xuống đoạn dốc cao nhất trong số đó rồi tiếp tục đi. Nếu không có đoạn nào như vậy, bạn rơi mãi mãi.

Đếm tổng số đoạn dốc bạn đã đi trên đó trong suốt hành trình.

Dữ liệu vào

  • Dòng 1: Số nguyên N
  • N dòng tiếp theo: Bốn số nguyên x1,y1,x2,y2 mô tả mỗi đoạn dốc

Dữ liệu ra

Số nguyên: tổng số đoạn dốc đã đi trên đó.

Ràng buộc

  • 1≤N≤100000
  • 0≤x1,y1,x2,y2≤109
  • x1<x2 và y1<y2 với mọi đoạn dốc
  • Không có hai đoạn dốc nào chạm nhau, kể cả tại đầu mút

Ví dụ

Input Output Giải thích
4
0 0 5 6
1 0 2 1
7 2 8 5
3 0 7 7
3 Đi trên đoạn 1 (0,0)→(5,6), rơi xuống đoạn 4 (3,0)→(7,7) vì tại x=5 đoạn này cao 5, thấp hơn 6. Đi tiếp tới (7,7), rơi xuống đoạn 3 (7,2)→(8,5), rồi rơi mãi mãi.
4
1 0 2 1
7 2 8 5
3 0 7 7
0 0 5 6
3 Cùng bốn đoạn dốc nhưng thứ tự khác. Điểm xuất phát (0,0) nằm trên đoạn số 4, không phải đoạn số 1.

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