• هفدهمین مسابقه‌ی برنامه نویسی اینترنتی ایران
  • مقدماتی منطقه‌ی غرب آسیا، سایت تهران
  • دانشگاه صنعتی شریف، ۷ آذر ۱۳۹۸

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

خیریه


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

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

اما در حین آماده‌سازی متوجه شد بیماری‌های دیگری نیز وجود دارند که فرآیند درمان آن‌ها بسیار هزینه بر است. به همین دلیل او تصمیم به ایجاد nn موسسه‌ی خیریه گرفت که هر کدام برای کمک به افراد مبتلا به یک بیماری خاص فعالیت کنند. علاوه بر این، سینا ساختاری برای این موسسسه‌ها ایجاد کرد تا کمک‌های مالی منحصر به یک بیماری نشوند. در این ساختار برای موسسه‌ی iiام، محدودیت مالی aia_i تومان در سال در نظر گرفته شده است. به این ترتیب اگر مجموع دریافتی موسسه‌ی ii ام از aia_i فراتر برود، مبلغ اضافه تا پایان سال به صورت خودکار به موسسه‌ی i+1i + 1 ام منتقل می‌شود. در صورتی که دریافتی سال جاری موسسه‌ی i+1i + 1 ام نیز به محدودیت مالی آن رسیده باشد، این روند ادامه پیدا می‌کند و مبلغ اضافه به موسسسه‌ی i+2i + 2 ام منتقل خواهد شد. اگر پس از اتمام محدودیت مالی موسسه‌ی nn ام کمکی به آن برسد، مبلغ دریافت شده به صورت جداگانه برای ایجاد موسسه های جدید ذخیره می‌شود.

متاسفانه با توجه به ساختار نوین این موسسه‌ها ابزار مناسبی برای رسیدگی به امور حساب داری آن وجود ندارد. بنابراین سینا از شما کمک خواسته است که یک برنامه‌ی حساب داری برای موسسه‌هایش پیاده سازی کنید. به طور دقیق‌تر برنامه‌ی شما باید به دو نوع درخواست پاسخ دهد:

  • ثبت کمک مردمی به مبلغ xx تومان به موسسه‌ی ppام.
  • اعلام موجودی موسسه‌ی kk ام.

به سینا کمک کنید تا تراکنش‌های مالی موسسه‌هایش را مدیریت کند.

ورودی🔗

در خط اول دو عدد nn و qq با یک فاصله آمده‌اند که به ترتیب تعداد موسسه‌های خیریه و تعداد درخواست‌ها را نشان می‌دهند.

1n,q2×1051 \leq n, q \leq 2 \times 10^5

در خط دوم nn عددهای a1,a3,,ana_1, a_3, \dots, a_n\, با فاصله آمده‌اند که محدودیت مالی موسسه‌ها را نشان می‌دهند. در ii امین خط از qq خط بعدی ابتدا یک عدد tit_i آمده است که نوع درخواست را نشان می‌دهد. اگر tit_i یک باشد، پس از آن دو عدد دیگر xix_i و pip_i آمده‌اند که به ترتیب موسسه‌ی هدف و میزان کمک در این تراکنش را نشان می‌دهند. در غیر این صورت tit_i برابر دو است و بعد از آن یک عدد kik_i آمده است که شماره‌ی موسسه‌ی خیریه‌ای است که موجودی آن درخواست شده است.

1pi,kin1 \leq p_i, k_i \leq n 1ai,xi1091 \leq a_i, x_i \leq 10^9

خروجی🔗

در خروجی به ازای هر درخواست از نوع دو یک خط چاپ کنید که موجودی موسسه‌ی درخواست شده در آن آماده است.

مثال🔗

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

3 6
15 20 18
1 1 22
2 2
1 1 16
1 3 12
2 2
2 3
Plain text

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

7
20
ٓ15
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.