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

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

مهره در گونی


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

آقای هاشمی nn گونی خالی در یک ردیف کنار هم گذاشته است. او گونی‌ها را با اعداد 11 تا nn به ترتیب از چپ به راست شماره‌گذاری کرده است.

او می‌خواهد در mm عملیات در این گونی‌ها مهره بریزد. او در عملیات iiام سه عدد lil_i، rir_i و xix_i را انتخاب می‌کند و سپس در همه‌ی گونی‌های بازه‌ی [li,ri][l_i, r_i] یک مهره xix_i می‌اندازد.

توضیح تصویر

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

ورودی🔗

در سطر اول ورودی دو عدد صحیح nn و mm که با یک فاصله از هم جدا شده‌اند آمده است. 1n,m5000001 \leq n, m \leq 500 \, 000 در mm سطر بعدی در هر سطر، سه عدد lil_i، rir_i و xix_i که با یک فاصله از هم جدا شده‌اند به ترتیب می‌آیند.

1lirin,1xi1091 \leq l_i \leq r_i \leq n, \quad \quad 1 \leq x_i \leq 10^9

خروجی🔗

در تنها سطر خروجی، nn عدد صحیح که با یک فاصله از هم جدا شده‌اند چاپ کنید. عدد iiام نشان دهنده‌ی پاسخ مسئله برای گونی iiام است.

مثال🔗

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

3 2
1 2 1
2 3 2
Plain text

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

2 3 1
Plain text

بعد از پایان این عملیات‌ها وضعیت مهره‌ها در هر گونی به صورت زیر است:

  • گونی 11: {1}\{1\}
  • گونی 22: {2,1}\{2, 1\}
  • گونی 33: {2}\{2\}

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

5 8
1 3 1
3 3 4
1 2 1
5 5 1
4 5 5
2 5 3
1 5 2
3 4 3
Plain text

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

3 4 5 1 4
Plain text

بعد از پایان این عملیات‌ها وضعیت مهره‌ها در هر گونی به صورت زیر است:

  • گونی 11: {1,1,2}\{1, 1, 2\}
  • گونی 22: {1,1,3,2}\{1, 1, 3, 2\}
  • گونی 33: {1,4,3,2,3}\{1, 4, 3, 2, 3\}
  • گونی 44: {5,3,2,3}\{5, 3, 2, 3\}
  • گونی 55: {1,5,3,2}\{1, 5, 3, 2\}
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.