لینک‌های مفید برای شرکت در مسابقه:

در طول مسابقه، می‌توانید سؤالات خود را از قسمت «سؤال بپرسید» مطرح کنید.

نوار مش‌رجب


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

مش‌رجب برای تولد ۶ سالگی خود یک نوار به طول nn هدیه گرفته است که در هر کدام از خانه‌های آن یک عدد مثبت نوشته شده است.

توضیح تصویر

در ابتدا تمامی خانه‌های این نوار آبی هستند. از آنجایی که مش‌رجب رنگ آبی را دوست ندارد، می‌خواهیم خانه‌های این نوار را برای او قرمز کنیم. می‌دانیم از نظر مش‌رجب میزان زیبایی یک بازه از نوار برابر با مجموع اعداد خانه‌های قرمز منهای اعداد خانه‌های آبی آن بازه است. همینطور میزان علاقه مش‌رجب به نوار برابر با بیشینه میزان زیبایی در میان تمام بازه‌های آن است.

می‌خواهیم یک به یک خانه‌های آبی را قرمز کنیم تا در نهایت تمام خانه‌ها قرمز شوند. از آنجا که مش‌رجب هنوز به مدرسه نرفته است و محاسبه حاصل جمع و تفریق کمی برایش سخت است، از شما می‌خواهیم که بگویید پس از قرمز شدن هر خانه، میزان علاقه مش‌رجب به نوار در آن لحظه چقدر است.

ورودی🔗

در خط اول ورودی عدد nn آمده است. در خط دوم nn عدد آمده است که عدد ii-ام آن‌‌‌‌ aia_i یا همان عدد خانه ii-ام ست. در خط سوم nn عدد آمده است که ترتیب قرمز شدن خانه‌ها را نمایش می‌دهد، اعداد این خط یک جایگشت از اعداد ۱ تا nn هستند.

1n1051 \le n \le 10^5

1ai1091 \le a_i \le 10^9

خروجی🔗

در تنها خط خروجی باید nn عدد چاپ کنید که عدد ii-ام نشان می‌دهد میزان علاقه مش‌رجب به نوار بعد از مرحله ii-ام چقدر است.

مثال🔗

ورودی نمونه ۱🔗

4
7 4 6 10
3 1 2 4
Plain text

خروجی نمونه ۱🔗

6 9 17 27 
Plain text

بعد از قرمز شدن خانه سوم نوار، زیبا‌ترین بازه از نظر مش‌رجب بازه‌ی [۳,۳] است و زیبایی ۶ دارد. وقتی خانه اول نیز قرمز می‌شود، زیباترین بازه از نظر مش‌رجب بازه [۱,۳] است که زیبایی ۹ دارد.

ورودی نمونه ۲🔗

10
4 2 7 6 4 2 6 3 1 7
8 3 1 6 2 7 10 4 5 9
Plain text

خروجی نمونه ۲🔗

3 7 9 9 13 14 20 32 40 42 
Plain text

ورودی نمونه ۳🔗

10
75 98 33 45 27 57 91 54 42 59 
8 6 5 9 1 2 7 10 3 4 
Plain text

خروجی نمونه ۳🔗

54 57 84 96 96 184 366 425 491 581 
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.