المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:دوره‌ی ۲۶:عملی مقدماتی دوم:سوال ۱

Gift

سروش در ابتدای صف ورود به سالن سینما، منتظر یکی از دوستانش است. دوست سروش در انتهای صف ایستاده و به دنبال او می‌گردد. به جز سروش و دوست او، $n$ نفر دیگر در صف، بین آن دو، ایستاده‌اند که از ابتدای صف به ترتیب با شماره‌های $1$ تا $n$ شماره‌گذاری شده‌اند.

با توجه به اینکه تمام این افراد صرفاً برای گذراندن وقت به سینما آمده بودند، تصمیم گرفتند به جای دیدن فیلم، کاری کنند که سروش و دوستش نتوانند یک‌دیگر را ببینند.

در هر لحظه تمامی افراد درون صف در یک جهت نگاه می‌کنند. جهت نگاه تمامی افراد در هر ثانیه یا به سمت سروش و ابتدای صف است و یا به سمت دوست او و انتهای صف. در هر ثانیه هر فرد اگر در راستایی که نگاه می‌کند، فرد دیگری که در حال حاضر از او اکیداً بلندتر باشد ببیند، قدش را به اندازه‌ی یک سانتی‌متر افزایش می‌دهد.

علی به مدت $m$ ثانیه این صحنه را نگاه می‌کند و به ازای هر یک از ثانیه‌ها جهت نگاه افراد را یادداشت می‌کند. به عبارت دقیق‌تر او به ازای هر عملیات یک حرف انگلیسی یادداشت می‌کند که اگر برابر L باشد افراد در ثانیه‌ی $i$ ام به سمت سروش و ابتدای صف نگاه می‌کنند و در صورتی که برابر R باشد، افراد در این ثانیه به سمت دوست سروش و انتهای صف نگاه می‌کنند.

او قد تمامی $n$ نفر را پیش از شروع عملیات‌های گفته شده، می‌داند. به عبارت دقیق‌تر، او می‌داند که قد نفر $i$ ام پیش از شروع عملیات‌ها $h_i$ سانتی‌متر است. برنامه‌ای بنویسید که با داشتن قد ابتدایی و جهت نگاه افراد در هر ثانیه، قد نهایی هر فرد را محاسبه کند.

ورودی

در خط اول ورودی دو عدد طبیعی $n$، تعداد افراد درون صف، و $m$، تعداد ثانیه‌هایی که علی عملیات گفته شده را مشاهده کرده، آمده است.

در خط دوم ورودی $n$ عدد $h_1, h_2, \ldots, h_n$ آمده است که قد ابتدایی افراد را نشان می‌دهند.

در خط سوم ورودی یک رشته‌ی به طول $m$ از حروف ‌R و L آمده است که حرف $i$ام این رشته، حرف نوشته‌ شده در ثانیه $i$ام را نشان می‌دهد.

خروجی

در تنها خط خروجی $n$ عدد چاپ کنید که عدد $i$ام قد نهایی فرد $i$ام را نشان می‌دهد.

زیرمسئله‌ها

  • زیرمسئله اول (۱۰۰ نمره): بدون محدودیت اضافی

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • $1 \le n, m \le 2 \times 10^5$
  • $0 \le h_i \le 10^9$

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
5 2
1 3 1 3 1
RL
2 3 3 3 2
5 4
5 4 3 2 1
LLRL
5 5 5 5 4

ابزار صفحه