תיאור
Helloooo! Can you hear me?
נתונה סדרה $A = (A_1, A_2, \dots, A_N)$ באורך $N$ המורכבת ממספרים שלמים הגדולים או שווים ל-$-1$. באמצעות סדרה זו ופרמטר $c$, בצעו את הפעולות הבאות:
- בהתחלה, קבעו את המשתנה $x := 0$.
- עבור $i = 1, 2, \dots, N$, חזרו על הפעולה הבאה:
- אם $A_i = -1$, עדכנו את $x$ להיות $x := \max(0, x - c)$.
- אחרת, עדכנו את $x$ להיות $x := x + A_i$.
ענו על $Q$ שאלות מהצורה הבאה:
- כאשר הפרמטר הוא $c = C_i$, מצאו את הערך המרבי שאליו מגיע $x$ לאורך כל סדרת הפעולות.
קלט
השורה הראשונה מכילה שני מספרים שלמים $N$ ו-$Q$ ($1 \le N, Q \le 3 \times 10^5$). השורה השנייה מכילה $N$ מספרים שלמים $A_i$ ($-1 \le A_i \le 10^6$). כל אחת מ-$Q$ השורות הבאות מכילה מספר שלם $C_i$, המייצג את ערך הפרמטר עבור השאלה ה-$i$ ($0 \le C_i \le 10^6$).
פלט
הדפיסו $Q$ שורות. בשורה ה-$i$, הדפיסו את התשובה לשאלה ה-$i$.
דוגמאות
קלט 1
20 11 50 100 50 100 0 200 -1 50 100 -1 200 -1 200 0 200 -1 200 200 -1 200 30 60 90 180 270 360 540 200 400 600 0
פלט 1
1700 1550 1400 950 570 500 500 850 500 500 1850
הערה
נסביר את השאלה הראשונה בקלט הדוגמה הראשונה:
- בשאלה זו, הפרמטר הוא $c = 30$.
- בהתחלה, $x = 0$.
- מכיוון ש-$A_1 = 50$, $x$ מתעדכן ל-$x = 0 + 50 = 50$.
- מכיוון ש-$A_2 = 100$, $x$ מתעדכן ל-$x = 50 + 100 = 150$.
- ...
- מכיוון ש-$A_6 = 200$, $x$ מתעדכן ל-$x = 300 + 200 = 500$.
- מכיוון ש-$A_7 = -1$, $x$ מתעדכן ל-$x = \max(0, 500 - 30) = 470$.
- ...
- מכיוון ש-$A_{19} = -1$, $x$ מתעדכן ל-$x = \max(0, 1530 - 30) = 1500$.
- מכיוון ש-$A_{20} = 200$, $x$ מתעדכן ל-$x = 1500 + 200 = 1700$.
כולל החלקים שהושמטו, הערך המרבי שאליו מגיע $x$ לאורך כל סדרת הפעולות הוא $1700$.