trang chủ / đề bài / icpc23_mt_h

Khám sức khỏe

Đề bài

Mô tả

Chi là một người bận rộn. Vì làm việc quá nhiều, Chi mắc một số bệnh cần được khám, và bác sĩ yêu cầu làm nhiều xét nghiệm để đánh giá sức khỏe của Chi.

Sau khi nhận yêu cầu, Chi xem lịch và thấy mình có n ngày rảnh sắp tới. Chi ghi chúng ra giấy thành dãy a1,a2,…,an, trong đó ai là khoảng cách (tính bằng ngày) từ hôm nay tới ngày rảnh thứ i. Ví dụ, nếu ngày mai rảnh thì a1=1.

Bác sĩ yêu cầu Chi đến bệnh viện làm m xét nghiệm. Chi chỉ có thể đến bệnh viện vào các ngày rảnh, nhưng có thể làm nhiều xét nghiệm khác nhau trong cùng một ngày. Với mỗi xét nghiệm, Chi cần z bộ hồ sơ để bác sĩ có thể kết luận bệnh.

Một bộ hồ sơ là một biểu đồ so sánh các chỉ số cơ thể giữa hai ngày khám nào đó để theo dõi tình trạng sức khỏe. Bộ hồ sơ hợp lệ khi khoảng cách giữa hai ngày khám nằm trong đoạn từ x đến y ngày. Bệnh viện chỉ cần đủ số bộ hồ sơ để kết luận bệnh và không cấm các bộ hồ sơ dùng chung ngày khám với nhau: dữ liệu của một ngày khám trước đó có thể được dùng để tạo nhiều bộ hồ sơ cho cùng một xét nghiệm. Nói cách khác, với một xét nghiệm, mỗi cặp ngày rảnh ai<aj có x≤aj−ai≤y cho một bộ hồ sơ, và bộ hồ sơ này có được từ ngày aj.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n,m.
  • Dòng thứ hai chứa n số nguyên dương tăng ngặt a1,a2,…,an: các ngày rảnh sắp tới của Chi.
  • m dòng tiếp theo, mỗi dòng chứa ba số nguyên x,y,z: yêu cầu Chi phải hoàn thành z bộ hồ sơ, mỗi bộ dùng hai ngày khám cách nhau từ x đến y ngày.

Dữ liệu ra

In ra ngày sớm nhất mà Chi hoàn thành tất cả các xét nghiệm. Nếu không có ngày như vậy, in ra −1.

Ràng buộc

  • 1≤n≤105, 1≤m≤103
  • 1≤a1<a2<…<an≤109
  • 1≤x≤y≤109, 1≤z≤109

Ví dụ

Input Output Giải thích
5 1
1 2 4 5 7
2 3 2
4 Chi làm 2 bộ hồ sơ: một bộ so sánh ngày 4 với ngày 1, một bộ so sánh ngày 4 với ngày 2. Sớm nhất hoàn thành vào ngày 4.
8 2
1 4 6 8 12 16 18 20
2 3 4
4 5 4
18 Xét nghiệm 1 hoàn thành sớm nhất vào ngày 18, xét nghiệm 2 hoàn thành sớm nhất vào ngày 16. In ra 18.

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