Phá Hủy Dãy Số (DSU Ngược)

Buổi 32 — Contest Chặng 4
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved