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

می‌توانید سوالات خود را از قسمت "سوال بپرسید" مطرح کنید.

سری چهارم راهنمایی‌ها به سوالات اضافه شد.

عاشق سرعت


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

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

هر مسافر در برنامه تپ‌نپ درخواستی به صورت (i,j)(i, j) می‌دهد و به این معنی است که می‌خواهد از میدان ii به میدان jj که j<ij < i است، برود.

متاسفانه برنامه‌ی مسیریاب آقا فیروز خراب شده‌ و مسافرین باید به او آدرس بدهند. مسافر در هر مرحله یک عدد kk به آقا فیروز می‌گوید و او به سمت چپ حرکت می‌کند تا به اولین میدانی برسد که ارتفاع مجسمه‌اش دقیقا kk متر باشد. مسافر طوری عدد را می‌گوید که چنین میدانی در سمت چپ میدان فعلی و قبل از میدان j1j - 1 وجود داشته باشد.

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

هم‌چنین آقا فیروز تا زمانی که یک مسافر را به مقصد نرسانده، او را پیاده نمی‌کند و در هر زمان دقیقا یک مسافر می‌تواند سوار ماشین شود.

آقا فیروز که به پول نیاز دارد، می‌خواهد ببیند اگر به ازای هر ii و jj که j<ij < i است، درخواست (i,j)(i, j) را قبول کند، در مجموع چقدر پول بدست می‌آورد؛ اما بدلیل اینکه رانندگی انرژی زیادی از وی می‌گیرد، او از شما درخواست کرده‌ تا شما برایش این مقدار را حساب کنید.

از آنجایی که ممکن است خروجی عددی بزرگ شود، جواب نهایی را به باقیمانده 109+710^9 + 7 خروجی دهید.

ورودی🔗

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

در خط دوم به ترتیب nn عدد h1,h2,h3,,hn h_1, h_2, h_3, \dots, h_n\ می‌آیند که hih_i برابر با ارتفاع مجسمه‌ای است که در میدان iiام قرار دارد. 1n100 000 1 \le n \le 100\ 000 1hi100 000 1 \le h_i \le 100\ 000

خروجی🔗

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

مثال🔗

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

3
4 1 2
Plain text

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

3
Plain text

درآمدی که آقا فیروز به ازای هر درخواست (i,j)(i, j) دارد به این‌صورت است:

  • (۲, ۱) = ۱
  • (۳, ۱) = ۱
  • (۳, ۲) = ۱

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

5
3 3 3 1 2
Plain text

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

17
Plain text

درآمدی که آقا فیروز به ازای هر درخواست (i,j)(i, j) دارد به این‌صورت است:

  • (۲, ۱) = ۱
  • (۳, ۱) = ۲
  • (۴, ۱) = ۳
  • (۵, ۱) = ۳
  • (۳, ۲) = ۱
  • (۴, ۲) = ۲
  • (۵, ۲) = ۲
  • (۴, ۳) = ۱
  • (۵, ۳) = ۱
  • (۵, ۴) = ۱
راهنمایی ۱

مسئله را به شکل زیر به یک گراف nn راسی تبدیل می‌کنیم که هر راس نماینده یک میدان است.

راس ii یالی مستقیم به راس jj دارد، اگر و تنها اگر j<ij<i و هیچ kk وجود نداشته باشد به صورتی که j<k<ij<k<i و hj=hkh_j=h_k باشد.

در این صورت جواب مسئله برابر با جمع فاصله هر دو راس است. حال سعی می‌کنیم این مقدار را در گراف ساخته شده محاسبه کنیم.

راهنمایی ۲

یال‌ها را برعکس نگاه می‌کنیم.

اگر kk کوچک‌ترین عددی باشد که i<ki<k و hi=hkh_i=h_k راس‌های i+1i+1 تا kk به راس ii یال دارند و اگر kk وجود نداشته باشد راس‌های i+1i+1 تا nn به راس ii یال دارند و اگر یال‌ها را برعکس کنیم راس ii به همه آن‌ها یال خواهد داشت.

پس یعنی راس ii به تعدادی از راس‌های جلوی خود یال دارد.

راهنمایی ۳

تعریف می‌کنیم: rir_i یعنی جلوترین راسی که راس ii به آن یال دارد.

در اصل راس ii به تمامی راس‌های i+1i+1 تا rir_i فاصله یک دارد.

ادعا می‌کنیم مسیر راس ii به راس‌های بزرگ‌تر از rir_i از راس jj می‌گذرد به صورتی که i<jrii<j \le r_i و rjr_j بیشینه است.

راهنمایی ۴

اولا که rir_i ها در واقع اولین مقدار بعد ii است که $a_r_i = a_i$ است.

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

سپس از روی مجموع فاصله‌های آن اندیس، می‌توان فاصله‌های جدید را هم به دست آورد.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.