Bài tập

Bài được chọn theo nhịp luyện tập của bạn, cùng mọi bài mới vừa lên.

Tối ưu

100 điểm

Thành phố Ngân là một trong những trung tâm đô thị phát triển bậc nhất, với mạng lưới giao thông hiện đại nhưng phức tạp. Hệ thống bao gồm $n$ nút giao thông (tượng trưng cho các ngã tư, vòng xuyến, hay điểm giao giữa các tuyến đường) và $m$ tuyến đường một chiều nối các nút này.

Tuy nhiên, dưới áp lực dân số tăng cao và sự phát triển kinh tế, chính quyền thành phố buộc phải đánh giá lại hệ thống hạ tầng và tìm giải pháp tối ưu hoá thời gian di chuyển trong nội đô. Việc này đòi hỏi các chuyên gia thuật toán, như bạn, tìm ra những cải tiến hiệu quả nhất với chi phí thấp nhất.

Mỗi tuyến đường trong thành phố là một đoạn một chiều cho phép đi từ nút $u_i$ đến nút $v_i$, và mất $t_i$ đơn vị thời gian để đi qua. Thành phố muốn tìm cách rút ngắn thời gian đi từ trung tâm hành chính (nút $1$) đến các khu vực khác (nút $s$) bằng cách **nâng cấp một tuyến đường bất kỳ**. Sau khi được nâng cấp, thời gian qua tuyến đó giảm còn đúng $t_0$.

**Lưu ý:** Chỉ được phép nâng cấp nhiều nhất một tuyến đường. Bạn không thể nâng cấp nhiều tuyến đường cùng lúc.

Input

Dòng đầu gồm ba số nguyên $n$, $m$, $q$ --- số nút, số tuyến đường, và số yêu cầu truy vấn $(1 \le n \le 2000,\ 1 \le m \le 10^4,\ 1 \le q \le 2 \cdot 10^6)$.
$m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $u_i$, $v_i$, $t_i$ --- mô tả tuyến đường đi từ $u_i$ đến $v_i$ với thời gian gốc là $t_i$ $(1 \le u_i, v_i \le n; u_i \ne v_i; 1 \le t_i \le 2000)$.
$q$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $s$ và $t_0$ --- tương ứng là điểm đến và thời gian sau khi nâng cấp $(1 \le s \le n; 1 \le t_0 \le 2000)$.

Output

Ghi ra $q$ dòng, dòng thứ $j$ là thời gian ngắn nhất để đi từ nút $1$ đến nút $s$ của truy vấn thứ $j$, khi được phép nâng cấp nhiều nhất một tuyến đường.

Nếu không thể đi từ nút $1$ đến nút $s$ (dù nâng cấp bất kỳ tuyến nào), in ra `-1`.

Example

Test 1

Input

Output

14
16
15

Scoring

Subtask 1 (30% số điểm): $n \le 20$, $q \le 200$.
Subtask 2 (40% số điểm): $n \le 200$, $q \le 2000$.
Subtask 3 (30% số điểm): $n \le 2000$, $q \le 2 \cdot 10^6$.

Xem thêm Thu gọn

0 Thích

root

Gọi hàm

100 điểm

iPrometheus là một lập trình viên. Anh ấy đang phát triển một chương trình lớn bằng ngôn ngữ lập trình Heraclosures, được sáng tạo bởi người bạn Heracles của mình. Chương trình này có $N$ hàm, mỗi hàm được đánh số từ $1$ đến $N$. Mỗi hàm có thể thực thi một số lệnh và thậm chí gọi các hàm khác.

Khi một hàm $i$ gọi hàm $j$, toàn bộ thời gian thực thi của hàm $j$ sẽ được tính vào thời gian thực thi của hàm $i$. Nếu một hàm không gọi bất kỳ hàm nào, thời gian thực thi của nó chỉ là thời gian cơ bản của chính nó. Để đảm bảo chương trình không gặp lỗi vòng lặp, Prometheus đã thiết kế để không có chu trình nào tồn tại trong các lời gọi hàm.

Mỗi hàm $i$ có:

Thời gian thực thi cơ bản $B_i$: thời gian cần thiết để thực thi hàm mà không bao gồm thời gian của các hàm khác mà nó gọi.
Danh sách các hàm được gọi trực tiếp $C(i)$: danh sách các hàm mà hàm $i$ gọi trực tiếp.

Thời gian thực thi tổng cộng của một hàm $i$ được định nghĩa là:
$
T(i) = B_i + \sum_{j \in C(i)} T(j)
$

Nếu $C(i)$ rỗng, tức là hàm $i$ không gọi hàm nào, khi đó $T(i) = B_i$.

Prometheus muốn thực hiện một số thay đổi và kiểm tra các hàm trong chương trình. Bạn cần viết một công cụ để hỗ trợ anh ấy thực hiện các thao tác sau:

Cập nhật: Thay đổi thời gian thực thi cơ bản $B_i$ của một hàm $i$ thành một giá trị mới $V$. Lưu ý rằng việc cập nhật $B_i$ không ảnh hưởng đến danh sách $C(i)$ của hàm $i$.
Truy vấn: Tính thời gian thực thi tổng cộng $T(i)$ của một hàm $i$ với các thay đổi hiện tại.

Cuối cùng, Prometheus không yêu cầu kết quả riêng cho từng truy vấn mà chỉ cần một giá trị tổng hợp. Nếu có $q$ truy vấn, hãy tính tổng:
$
\text{Kết quả} = \left( \sum_{k=1}^q k \cdot T(i_k) \right) \mod (10^9 + 7)
$

trong đó $T(i_k)$ là thời gian thực thi của hàm được truy vấn ở lần thứ $k$.

Input

Dữ liệu đầu vào bao gồm:

Dòng đầu tiên chứa một số nguyên $N$ $(1 \leq N \leq 8000)$ --- số lượng hàm trong chương trình.
Dòng thứ hai chứa $N$ số nguyên $B_1, B_2, \dots, B_N$ $(0 \leq B_i \leq 10^9)$ --- thời gian thực thi cơ bản của các hàm.
Dòng thứ ba chứa một số nguyên $M$ $(1 \leq M \leq 8000)$ --- số lượng lời gọi giữa các hàm.
Mỗi dòng trong $M$ dòng tiếp theo chứa hai số nguyên $F$ và $G$ $(1 \leq F, G \leq N, F \neq G)$, biểu thị rằng hàm $F$ gọi trực tiếp hàm $G$.
Dòng tiếp theo chứa một số nguyên $E$ $(1 \leq E \leq 10^6)$ --- số lượng sự kiện (cập nhật hoặc truy vấn).
Mỗi dòng trong $E$ dòng tiếp theo là một sự kiện:
U I V: Cập nhật thời gian thực thi cơ bản của hàm $I$ thành $V$ $(0 \leq V \leq 10^9)$.
Q J: Truy vấn thời gian thực thi tổng cộng của hàm $J$ $(1 \leq J \leq N)$.

Bảo đảm rằng:

Không có chu trình nào tồn tại trong các lời gọi giữa các hàm.
Luôn có ít nhất một truy vấn trong danh sách sự kiện.

Output

In ra một số nguyên duy nhất --- kết quả tổng hợp của tất cả các truy vấn.

Example

Test 1

Input

Output

Note

Test $1$ : $230$, $120$, $100$.

Test $2$ : $94$, $42$, $42$, $84$.

Test 2

Input

Output

Scoring

$25\%$ số test có $n, m, E \leq 100$.
$25\%$ số test có $n, m \leq 8000, E \leq 8000$.
$25\%$ số test có $m = n - 1, F = i, G = i + 1$.
$25\%$ số test còn lại không có ràng buộc gì thêm.

Xem thêm Thu gọn

0 Thích

root

Ăng-ten

100 điểm

Có $N$ ăng-ten được đánh số từ $1$ đến $N$ và được đặt thẳng hàng trên một trục, mỗi cái cách nhau đúng $1$ km. Ăng-ten thứ $i$ có chiều cao là $H_i$ và có thể truyền tín hiệu đến các ăng-ten nằm trong đoạn từ $A_i$ đến $B_i$ (tính theo khoảng cách từ vị trí $i$).

Cụ thể hơn, ăng-ten $x$ và $y$ $(1 \le x < y \le N)$ có thể truyền thông tin cho nhau nếu và chỉ nếu:

$x$ nằm trong đoạn mà $y$ có thể truyền tới, và
$y$ nằm trong đoạn mà $x$ có thể truyền tới.

Khi đó, hai ăng-ten được gọi là có thể liên lạc được, và chi phí liên lạc giữa hai ăng-ten này được tính là $|H_x - H_y|$.

Thủ tướng K nhận được $Q$ khiếu nại từ người dân về việc liên lạc kém. Mỗi khiếu nại liên quan đến một đoạn ăng-ten liên tiếp từ $L_j$ đến $R_j$. Với mỗi khiếu nại, hãy xác định xem có cặp ăng-ten nào trong đoạn đó có thể liên lạc được không. Nếu có, hãy in ra chi phí liên lạc lớn nhất giữa các cặp như vậy. Nếu không có cặp nào thỏa mãn, in ra $-1$.

\InputFile

Dòng đầu chứa số nguyên $N$ ($2 \le N \le 200\,000$).
$N$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $H_i$, $A_i$, $B_i$ ($1 \le H_i \le 10^9$, $1 \le A_i \le B_i \le N - 1$).
Dòng tiếp theo chứa số nguyên $Q$ ($1 \le Q \le 200\,000$).
$Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L_j, R_j$ ($1 \le L_j < R_j \le N$).

\OutputFile

In ra $Q$ dòng. Dòng thứ $j$ in ra $-1$ nếu không tồn tại cặp ăng-ten nào trong đoạn $[L_j, R_j]$ có thể liên lạc với nhau. Ngược lại, in ra chi phí liên lạc lớn nhất giữa các cặp liên lạc được.

\Scoring

Subtask 1 (10%): $N, Q \le 300$
Subtask 2 (25%): $N \le 2000$
Subtask 3 (25%): $Q = 1$, $L_1 = 1$, $R_1 = N$
Subtask 4 (40%): Không có ràng buộc bổ sung

Example

Test 1

Input

Output

Xem thêm Thu gọn

0 Thích

root

Chặt gỗ

100 điểm

Quân đang cần gấp $M$ mét gỗ để đốt củi sưởi ấm mùa đông. May mắn là anh có một cái máy cưa có thể cắt mọi thứ, ở bất kì độ cao nào.

Máy cưa sẽ hoạt động như sau: Lúc đầu Quân sẽ chỉnh độ cao cắt của máy cưa, gọi độ cao đó là $H$. Sau đó, máy cưa sẽ tự động bay lên, cắt một đường ngang, cây nào có độ cao lớn hơn $H$ sẽ bị cắt trúng, và phần gỗ rơi xuống Quân sẽ lấy đi để đốt.

Ví dụ nếu các cây có độ cao lần lượt là $20, 15, 15, 20, 25$, và $H = 15$ thì cây thứ nhất và cây thứ tư mỗi cây bị cắt mất $5$ m, cây thứ $5$ bị cắt mất $10$ m, tổng cộng là $20$ m.

Yêu cầu: Hãy xác định độ cao $H$ lớn nhất sao cho cắt ở độ cao $H$ thì Quân sẽ thu được ít nhất $M$ mét gỗ. Nếu cắt trụi $N$ cây mà vẫn không đủ $M$ mét gỗ, in ra $-1$.

Input

Dòng đầu tiên chứa số nguyên dương $N$ - số lượng cây.
Dòng thứ hai chứa $N$ số nguyên dương $a_{1}, a_{2}, ..., a_{N}$ - độ cao lần lượt của các cây.

Output

Kết quả bài toán.

Example

Test 1

Input

4 7
20 15 10 17

Output

Test 2

Input

5 20
4 42 40 26 46

Output

Scoring

$50\%$ số test có $N \leq 1000$, độ cao lớn nhất của các cây không vượt quá $1000$ m.
$50\%$ số test còn lại có $N \leq 10^6$, độ cao lớn nhất của các cây không vượt quá $10^9$ m.

Đảm bảo trong tất cả các test, $M \leq 10^9$.

Xem thêm Thu gọn

0 Thích

Xem thêm

Điều hướng chính

Ngôn ngữ

Phím tắt

Bài tập

Tối ưu

Input

Output

Example

Scoring

Gọi hàm

Input

Output

Example

Scoring

Ăng-ten

Example

Chặt gỗ

Input

Output

Example

Scoring