Chia Cụm Ổn Định

Buổi 39 — DP + Data Structures Dynamic Programming two-pointers
Points
75
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho một dãy gồm $N$ ô đánh số từ $1$ đến $N$, ban đầu tất cả các ô đều có màu 0. Thực hiện tuần tự $Q$ thao tác, thao tác thứ $i$ tô tất cả các ô trong đoạn $[L_i, R_i]$ thành màu $C_i$ (màu mới sẽ ghi đè lên màu cũ). Hãy in ra màu cuối cùng của tất cả $N$ ô từ $1$ đến $N$.

Dữ liệu vào
Input Output 6 2 2
1 2 4 5 5 6 2 5 3 1
1 5 2 6 3 -1
Giới hạn
  • $1 \le L \le N \le 10^5$
  • $0 \le D \le 10^9$
  • $-10^9 \le A_i \le 10^9$
Draft saved