Xếp giấy

Xem dạng PDF

Gửi bài giải

Điểm: 800 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Dạng bài
Ngôn ngữ cho phép
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, PyPy, Python, Racket, Ruby, Rust, Scala, Scheme, Scratch, Sed, Swift, TCL, Turing, VB, Zig

vvngh có ~N~ tờ giấy kích thước khác nhau. Cậu ấy nghĩ ra một trò chơi thú vị. vvngh xếp những tờ giấy ở chân tường sát lại gần nhau theo thứ tự. vvngh quan sát và nhận thấy tờ giấy thứ ~i~ có chiều rộng ~w_i~ ô ly và chiều cao ~h_i~ ô ly. vvngh thắc mắc rằng liệu có bao nhiêu hình chữ nhật tạo được từ các ô ly của những tờ giấy khi xếp lại. Nhiệm vụ của bạn là giúp cậu ấy giải đáp thắc mắc này.

~\texttt{Input}~

  • Dòng đầu tiên chứa số nguyên ~N~ là số lượng tờ giấy.
  • ~N~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~h_i~ và ~w_i~ biểu diễn chiều cao và chiều rộng của tờ giấy thứ ~i~

~\texttt{Output}~

  • Gồm một số nguyên duy nhất là kết quả của bài toán.
  • Vì kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho ~10^9 + 7~.

~\texttt{Constraint}~

  • ~1 \leq N \leq 10^5~
  • ~1 \leq w_i~, ~h_i \leq 10^9~

~\texttt{Subtask}~

  • Subtask ~1~ (~25\%~ số điểm): ~h_i = h_{i+1}~ với mọi ~i < N~.
  • Subtask ~2~ (~25\%~ số điểm): ~h_i \leq h_{i+1}~ với mọi ~i < N~.
  • Subtask ~3~ (~25\%~ số điểm): ~N \leq 1000~
  • Subtask ~4~ (~25\%~ số điểm): Không có giới hạn gì thêm

~\texttt{Sample Input}~

3
3 1
2 1
1 1

~\texttt{Sample Output}~

15

~\texttt{Note}~

  • Có ~6~ hình chữ nhật kích thước ~1\times1~.
  • Có ~3~ hình chữ nhật kích thước ~2\times1~.
  • Có ~3~ hình chữ nhật kích thước ~1\times2~.
  • Có ~1~ hình chữ nhật kích thước ~2\times2~.
  • Có ~1~ hình chữ nhật kích thước ~3\times1~.
  • Có ~1~ hình chữ nhật kích thước ~1\times3~.

Vậy kết quả của ví dụ đầu tiên là ~6 + 3 + 3 + 1 + 1 + 1 = 15~


Bình luận

Hãy đọc nội quy trước khi bình luận.


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