آب

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

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

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

ورودی🔗

در سطر اوّل ورودی عدد طبیعی $n$ (تعداد ساختمان‌ها) آمده است.

در سطر بعد $n$ عدد آمده است که به ترتیب ارتفاع ساختمان‌ها را از راست به چپ مشخّص می‌کنند و با space از هم جدا شده اند.

ارتفاع هر ساختمان حداکثر ۱۰۰۰ متر خواهد بود. $1 \leq n \leq 1\ 000\ 000$

خروجی🔗

در تنها خط خروجی حداکثر میزان آب جمع شده روی سقف ساختمان‌های شهر آنیتا (بر حسب متر مربّع) بنویسید.

مثال🔗

ورودی نمونه🔗

7
4 1 3 5 2 3 4

خروجی نمونه🔗

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ***** در یک صف $n$ سرباز با شماره‌های ۱ تا $n$ ایستاده‌اند. سرباز $i$ام در ابتدا $S_i$ نشان لیاقت(مدال) روی سینه‌اش دارد. طی مراسمی $m$ ژنرال می‌خواهند به این سربازها مدال‌های جدید بدهند. می‌دانیم ژنرال $i$ام به سربازانی که شماره‌شان در بازه‌ی $\left[ a_i, b_i\right]$ باشد مدال خواهد داد. هم‌چنین می‌دانیم اگر بازه‌های دو ژنرال مثل $x$ و $y$ با هم اشتراک داشته باشند، نمی‌توان دو سرباز مثل $u$ و $v$ یافت که $u$ فقط از $x$(و نه از $y$) و $v$ فقط از $y$(و نه از $x$) مدال گرفته باشد. مجری مراسم می‌خواهد زیرمجموعه‌ای از ژنرال‌ها را به مراسم دعوت کند که در پایان مراسم(پس از اهدای مدال‌ها) تعداد سربازهایی که فرد مدال دارند(با احتساب مدال‌های اوّلیّه) بیشینه شود. این مقدار بیشینه را پیدا کنید! شما باید به ازای $t$ سناریو جواب را پیدا کنید. # ورودی در سطر اوّل ورودی عدد طبیعی $t$ آمده است. به ازای هر سناریو، در سطر اوّل $n$ و در سطر پس از آن $S_i$ها به ترتیب آمده‌اند. سپس در سطر بعد $m$ آمده است؛ در سطر بعد $2m$ عدد نوشته شده است که عدد $2i - 1$ام، $a_i$ و عدد $2i$ام برابر $b_i$ خواهد بود. $$1\leq t \leq 20$$ به طور کلّی $1\leq n,m \leq 100\ 000$ ولی در ۳۰ درصد از تست‌ها شرط $1\leq n,m \leq 2\ 000$ برقرار خواهد بود. $$1 \leq a_i \leq b_i \leq n$$ تمامی اعداد ورودی صحیح، نامنفی و حداکثر برابر $10^9$ خواهند بود. # خروجی جواب هر سناریو(حداکثر تعداد سربازها با شرایط مذکور) را به ترتیب در خط‌های جدا از هم بنویسید. # مثال ## ورودی نمونه ``` 2 3 8 9 0 3 1 3 1 1 1 1 4 7 6 8 2 3 1 4 1 1 4 4 ``` ## خروجی نمونه ``` 2 4 ```

مدال

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

در یک صف $n$ سرباز با شماره‌های ۱ تا $n$ ایستاده‌اند. سرباز $i$ ام در ابتدا $S_i$ نشان لیاقت(مدال) روی سینه‌اش دارد.

طی مراسمی $m$ ژنرال می‌خواهند به این سربازها مدال‌های جدید بدهند. می‌دانیم ژنرال $i$ ام به سربازانی که شماره‌شان در بازه‌ی $\left[ a_i, b_i\right]$ باشد مدال خواهد داد. هم‌چنین می‌دانیم اگر بازه‌های دو ژنرال مثل $x$ و $y$ با هم اشتراک داشته باشند، نمی‌توان دو سرباز مثل $u$ و $v$ یافت که $u$ فقط از $x$ (و نه از $y$ ) و $v$ فقط از $y$ (و نه از $x$ ) مدال گرفته باشد.

مجری مراسم می‌خواهد زیرمجموعه‌ای از ژنرال‌ها را به مراسم دعوت کند که در پایان مراسم(پس از اهدای مدال‌ها) تعداد سربازهایی که فرد مدال دارند(با احتساب مدال‌های اوّلیّه) بیشینه شود. این مقدار بیشینه را پیدا کنید!

شما باید به ازای $t$ سناریو جواب را پیدا کنید.

ورودی🔗

در سطر اوّل ورودی عدد طبیعی $t$ آمده است.

به ازای هر سناریو، در سطر اوّل $n$ و در سطر پس از آن $S_i$ ها به ترتیب آمده‌اند.

سپس در سطر بعد $m$ آمده است؛ در سطر بعد $2m$ عدد نوشته شده است که عدد $2i - 1$ ام، $a_i$ و عدد $2i$ ام برابر $b_i$ خواهد بود.

$1\leq t \leq 20$

به طور کلّی $1\leq n,m \leq 100\ 000$ ولی در ۳۰ درصد از تست‌ها شرط $1\leq n,m \leq 2\ 000$ برقرار خواهد بود.

$1 \leq a_i \leq b_i \leq n$

تمامی اعداد ورودی صحیح، نامنفی و حداکثر برابر $10^9$ خواهند بود.

خروجی🔗

جواب هر سناریو(حداکثر تعداد سربازها با شرایط مذکور) را به ترتیب در خط‌های جدا از هم بنویسید.

مثال🔗

ورودی نمونه🔗

2
3
8 9 0
3
1 3 1 1 1 1
4
7 6 8 2
3
1 4 1 1 4 4

خروجی نمونه🔗

2
4

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ***** ماتریس طلایی ماتریسی‌است $n \times n$ که اعداد آن صحیح، نامنفی و متمایز باشند. روی یک ماتریس طلایی می‌توانیم هر یک از عملیات زیر را به تعداد دلخواه انجام دهیم تا به ماتریس جدیدی تبدیل شود. ۱. عمل $A$: دو سطر ماتریس را با هم جابه‌جا کنیم. ۲. عمل $B$: خانه‌های یک سطر را یک واحد شیفت دورانی بدهیم. (یعنی مقدار خانه‌ی $i$ام آن به خانه‌ی $\left(i + 1\right) \mod n $ برود. (به ازای هر $i$ که $0\leq i < n$) ۳. عمل $C$: به تمام خانه‌های ماتریس یک مقدار صحیح و مثبت را اضافه کنیم. ۴. عمل $D$: مقدار تمام خانه‌های ماتریس را به توان ۲ برسانیم. دقّت کنید که این ۴ عمل به ترتیب ۲ و ۱ و ۱ و صفر پارامتر دارند. پارامترهای دو عمل $A$ و $B$ باید در محدوده‌ی $\left[0, n\right)$ باشند. پارامتر عمل $C$ نیز باید از $1$ تا $10^9$ باشد. می‌گوییم ماتریس $X$ نوه‌ی ماتریس طلایی $G$ است اگر بتوان با متناهی بار اِعمالِ اَعمال بالا روی $G$ به $X$ رسید. ماتریس‌های $X$ و $Y$ را نیز پسرخاله می‌نامیم، اگر و فقط اگر ماتریسی مثل $G$ پیدا شود که $X$ و $Y$ نوه‌ی آن باشند. به ازای $T$ سناریو، دو ماتریس $X$ و $Y$ به شما می‌دهیم، باید بگویید که آیا آن دو پسرخاله هستند یا نه. # ورودی در سطر اوّل ورودی عدد طبیعی $T$ آمده است. به ازای هر سناریو: در خط اوّل عدد $n$ آمده است. در $n$ سطر بعدی، در هر سطر $n$ عدد آمده است. عدد $j$ام در سطر $i$ام برابر $X_{i,j}$ خواهد بود. پس از ماتریس $X$، ماتریس $Y$ نیز به همین صورت در $n$ خط بعد از آن خواهد آمد. اعداد داخل هر سطر با space از هم جدا شده اند.$$1\leq T\leq20$$ $$1\leq n \leq 1\ 000$$ تمام اعداد ورودی صحیح، نامنفی و حداکثر برابر $10^9$ خواهند بود. هر یک از دو ماتریس هر سناریو طلایی هستند و اعداد داخل هر یک متمایز هستند. # خروجی به ازای هر سناریو در یک خط باید `Yes`(در صورتی که دو ماتریس پسرخاله بودند) یا `No`(در صورتی که دو ماتریس پسرخاله نبودند) بنویسید. # مثال ## ورودی نمونه ``` 2 2 1 0 2 3 10 5 1 2 3 10 20 30 1 2 3 9 7 8 1 4 9 100 400 900 49 64 80 ``` ## خروجی نمونه ``` Yes No ```

ماتریس

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

ماتریس طلایی ماتریسی‌است $n \times n$ که اعداد آن صحیح، نامنفی و متمایز باشند.

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

۱. عمل $A$ : دو سطر ماتریس را با هم جابه‌جا کنیم.

۲. عمل $B$ : خانه‌های یک سطر را یک واحد شیفت دورانی بدهیم. (یعنی مقدار خانه‌ی $i$ ام آن به خانه‌ی $\left(i + 1\right) \mod n$ برود. (به ازای هر $i$ که $0\leq i < n$ )

۳. عمل $C$ : به تمام خانه‌های ماتریس یک مقدار صحیح و مثبت را اضافه کنیم.

۴. عمل $D$ : مقدار تمام خانه‌های ماتریس را به توان ۲ برسانیم.

دقّت کنید که این ۴ عمل به ترتیب ۲ و ۱ و ۱ و صفر پارامتر دارند. پارامترهای دو عمل $A$ و $B$ باید در محدوده‌ی $\left[0, n\right)$ باشند. پارامتر عمل $C$ نیز باید از $1$ تا $10^9$ باشد.

می‌گوییم ماتریس $X$ نوه‌ی ماتریس طلایی $G$ است اگر بتوان با متناهی بار اِعمالِ اَعمال بالا روی $G$ به $X$ رسید.

ماتریس‌های $X$ و $Y$ را نیز پسرخاله می‌نامیم، اگر و فقط اگر ماتریسی مثل $G$ پیدا شود که $X$ و $Y$ نوه‌ی آن باشند.

به ازای $T$ سناریو، دو ماتریس $X$ و $Y$ به شما می‌دهیم، باید بگویید که آیا آن دو پسرخاله هستند یا نه.

ورودی🔗

در سطر اوّل ورودی عدد طبیعی $T$ آمده است.

به ازای هر سناریو: در خط اوّل عدد $n$ آمده است. در $n$ سطر بعدی، در هر سطر $n$ عدد آمده است. عدد $j$ ام در سطر $i$ ام برابر $X_{i,j}$ خواهد بود. پس از ماتریس $X$ ، ماتریس $Y$ نیز به همین صورت در $n$ خط بعد از آن خواهد آمد.

اعداد داخل هر سطر با space از هم جدا شده اند. $1\leq T\leq20$ $1\leq n \leq 1\ 000$

تمام اعداد ورودی صحیح، نامنفی و حداکثر برابر $10^9$ خواهند بود.

هر یک از دو ماتریس هر سناریو طلایی هستند و اعداد داخل هر یک متمایز هستند.

خروجی🔗

به ازای هر سناریو در یک خط باید Yes(در صورتی که دو ماتریس پسرخاله بودند) یا No(در صورتی که دو ماتریس پسرخاله نبودند) بنویسید.

مثال🔗

ورودی نمونه🔗

2
2
1 0
2 3
10 5
1 2
3
10 20 30
1 2 3
9 7 8
1 4 9
100 400 900
49 64 80

خروجی نمونه🔗

Yes
No