عسل با دوست‌های خوب و شیطونش


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

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

یک مثلث قائم‌الزاویه n×nn \times n داریم. مثلث از nn ستون تشکیل شده که ستون iiام آن، nin - i سطر دارد. در mm تا از خانه‌های مثلث مربّا و در بقیه خانه‌های آن عسل قرار داده شده است. یک زیرمثلث kkتایی نشان‌گر اشتراک خانه‌های kk سطر و kk ستون متناظر آن‌ها از مثلث است. یک زیرمثلث خوب، زیرمثلثی‌است که در تمام خانه‌های آن مربّا قرار دارد. همچنین زیرمثلث دوست‌داشتنی زیر‌مثلثی‌است که به ازای هر سطر آن، در اجتماع خانه‌های آن سطر و ستون متناظرش دو مربّا وجود داشته باشد. علاوه بر این یک زیرمثلث عجیب، زیرمثلثی‌ است که دوست‌داشتنی باشد، ولی هیچ زیرمثلثی از آن دوست‌داشتنی نباشد.

تعداد زیرمثلث‌های kkتایی خوب مثلث برابر با f(k)f(k) است. بزرگ مربّاها از آن‌ها خواست تا مقدار Σi=1nf(i)×(1)i+1\Sigma_{i = 1}^n f(i) \times (-1)^{i+1} را بیابند. مربّاها که از شنیدن این معما گیج شده بودند، از بزرگ مربّاها خواستند تا کمکی به آن‌ها بکند. بزرگ مربّاها کمی فکر کرد و سپس به مربّاها گفت که کاری می‌کند که اگر زیرمثلث kkتایی عجیب در مثلث بود، k3k \leq 3 باشد.

مربّاها بعد از این که بزرگشان این شرط را روی مثلث گذاشت، باز هم نتوانستند مسئله را حل کنند، برای همین باز هم دست به دامن شما شدند. لطفا به آن‌ها کمک کنید تا مسئله را حل کنند.

ورودی🔗

در اولین خط ورودی، nn که نشان‌دهنده‌ی اندازه‌ی مثلث است و mm که تعداد مربّاهای داخل مثلث است، می‌آید. در ادامه mm خط می‌آید که در خط iiام، rir_i و cic_i آمده است که به ترتیب سطر و ستون خانه‌ی مربّای iiام را نشان می‌دهد. 1n100 0001 \leq n \leq 100\ 000 0m1000 0000 \leq m \leq 1000\ 000 1ci<rin1 \leq c_i < r_i \leq n

خروجی🔗

در تنها خط خروجی، مقداری که بزرگ مربّا در معما خواسته را خروجی دهید.

مثال🔗

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

3 2
1 2
1 3
Plain text

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

1
Plain text

مجموعه شماره سطرهایی که زیرمثلث خوب می‌سازند عبارتند از:

  • {1}\{1\}
  • {2}\{2\}
  • {3}\{3\}
  • {1,2}\{1, 2\}
  • {1,3}\{1, 3\}
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.