Bedao Grand Contest 13 - MAXSEG

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

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

Cho dãy ~a~ gồm ~n~ phần tử nguyên và một hoán vị ~p~ độ dài ~n~.

Ta thực hiện một trò chơi gồm ~n~ bước như sau: ở bước thứ ~i~, ta xóa đi phần tử ~p_i~.

Yêu cầu: Trước khi thực hiện mỗi bước, hãy in ra tổng lớn nhất của đoạn con gồm các phần tử liên tiếp, có độ dài lớn hơn ~0~ và chưa có phần tử nào bị xóa trên dãy ~a~.

Input

  • Dòng đầu tiên chứa số nguyên dương ~n~ miêu tả độ dài dãy ~a~ và hoán vị ~p~ ~(1 \le n \le 5*10^5)~.

  • Dòng thứ hai gồm ~n~ số nguyên miêu tả dãy ~a_1,a_2,...,a_n~ ~( |a_i| \le 10^9)~

  • Dòng thứ ba gồm ~n~ số nguyên dương miêu tả dãy hoán vị ~p_1,p_2,...,p_n~

Output

  • Gồm ~n~ dòng, dòng thứ ~i~ in ra giá trị của đoạn con gồm các phần tử liên tiếp chưa có phần tử nào bị xóa và có tổng lớn nhất trước bước thứ ~i~.

Scoring

  • Subtask ~1~ (~30~ điểm): ~n \le 5000~

  • Subtask ~2~ (~30~ điểm): ~a_i > 0~

  • Subtask ~3~ (~40~ điểm): Không ràng buộc gì thêm.

Sample Input 1

7
4 -1 2 -3 4 -2 3
6 1 5 2 7 4 3

Sample Output 1

7
6
4
3
3
2
2

Notes

  • Trước khi thực hiện thao tác ~1~, dãy là [~4~, ~-1~, ~2~, ~-3~, ~4~, ~-2~, ~3~], đoạn con lớn nhất thỏa mãn là ~[1,7]~

  • Trước khi thực hiện thao tác ~2~, dãy là [~4~, ~-1~, ~2~, ~-3~, ~4~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[1,5]~

  • Trước khi thực hiện thao tác ~3~, dãy là [~*~, ~-1~, ~2~, ~-3~, ~4~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[5,5]~

  • Trước khi thực hiện thao tác ~4~, dãy là [~*~, ~-1~, ~2~, ~-3~, ~*~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[7,7]~

  • Trước khi thực hiện thao tác ~5~, dãy là [~*~, ~*~, ~2~, ~-3~, ~*~, ~*~, ~3~], đoạn con lớn nhất thỏa mãn là ~[7,7]~

  • Trước khi thực hiện thao tác ~6~, dãy là [~*~, ~*~, ~2~, ~-3~, ~*~, ~*~, ~*~], đoạn con lớn nhất thỏa mãn là ~[3,3]~

  • Trước khi thực hiện thao tác ~7~, dãy là [~*~, ~*~, ~2~, ~*~, ~*~, ~*~, ~*~], đoạn con lớn nhất thỏa mãn là ~[3,3]~


Comments

Please read the guidelines before commenting.



  • 8
    hungntils  commented on June 28, 2023, 3:05 p.m.

    Nguồn: https://codeforces.com/contest/722/problem/C


    • -2
      OrzSeaPosjtive  commented on June 30, 2023, 8:06 a.m.

      cảm ơn bạn dù 2 bài nó không được giống nhau lắm :))))


  • -7
    dangbesttoan24  commented on June 28, 2023, 2:31 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.