Phá Hủy Dãy Số (DSU Ngược)
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho dãy gồm $N$ số nguyên không âm $A_1, A_2, \dots, A_N$. Ở mỗi bước từ $1$ đến $N$, ta xóa phần tử tại vị trí $P_i$ (trong đó $P_1, P_2, \dots, P_N$ là một hoán vị của $1..N$).
Sau mỗi lần xóa, một số đoạn con liên tiếp gồm các phần tử chưa bị xóa được hình thành. Hãy in ra tổng lớn nhất trong các đoạn con liên tiếp còn lại sau mỗi bước xóa (nếu không còn phần tử nào thì tổng là 0).
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 2 \cdot 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $A_1, \dots, A_N$ ($0 \le A_i \le 10^9$).
- Dòng thứ ba chứa hoán vị $P_1, \dots, P_N$.
Dữ liệu ra
- Gồm $N$ dòng, dòng thứ $i$ là tổng đoạn liên tiếp lớn nhất sau khi xóa $P_i$.
Ví dụ
| Input | Output |
|---|---|
| 4 1 3 2 5 3 4 1 2 |
5 4 3 0 |
Giới hạn
- $1 \le N \le 2 \cdot 10^5$
Community Discussion