Bedao Regular Contest 18 - Thành phố đông dân nhất

View as PDF

Submit solution


Points: 0.90 (partial)
Time limit: 3.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Đất nước Alpha bao gồm ~n~ thành phố. Hiện tại, các thành phố được đánh số từ ~1~ đến ~n~, ở thành phố thứ ~i~ đang có dân số là ~a_i~.

Sắp tới, để cải cách lại đất nước, nhà vua quyết định sẽ hợp nhất một số thành phố lại với nhau. Các đại thần đã dâng lên nhà vua ~m~ đề xuất, trong đề xuất thứ ~i~, hai thành phố ~x_i~ và ~y_i~ sẽ được hợp nhất lại với nhau.

Sau khi nhận được đề xuất của các vị đại thần, nhà vua lập ra ~q~ kế hoạch, trong kế hoạch thứ ~i~, những lời đề xuất của các vị đại thần từ ~l_i~ đến ~r_i~ sẽ được chấp nhận. Để đánh giá độ hiệu quả của một kế hoạch, nhà vua muốn biết rằng sau khi sát nhập, thành phố có dân số nhiều nhất là bao nhiêu.

Với tư cách là tân trạng nguyên của đất nước Alpha, nhà vua đã giao cho bạn công việc khó nhằn này. Bạn hãy giúp nhà vua đánh giá độ hiệu quả của các kế hoạch hoặc bị tr...

Input

Dòng đầu tiên chứa ba số nguyên ~n~, ~m~, ~q~ (~1\le n, m, q \le 2\times 10^5~ ).

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^4~ ).

Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa hai số nguyên ~x_i, y_i~ (~1\le x_i, y_i \le n~ ) — đề xuất của đại thần ~i~ .

Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa hai số nguyên ~l_i, r_i~ (~1\le l_i, r_i \le m~ ) — kế hoạch thứ ~i~ của nhà vua.

Output

Với mỗi kế hoạch, in ra dân số lớn nhất của một thành phố sau khi thực hiện kế hoạch trên một dòng.

Scoring

Subtask Điểm Giới hạn
1 ~10~ Đồ thị là dạng đường thẳng, ~m = n-1~, các cạnh có dạng ~(i,i+1)~
2 ~20~ ~n,m,q \le 3000~
3 ~70~ Không có ràng buộc nào.

Sample Input 1

6 7 4
6 4 2 7 1 13
5 3
2 5
2 3
1 2
1 6
4 3
5 4
1 3
5 7
1 4
6 7

Sample Output 1

13
19
13
13

Sample Input 2

2 1 1
1 1
1 2
1 1

Sample Output 2

2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.