المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۷۴

WC

‎$N$‎ تماشاچی در صف مسابقه استقلال و پرسپولیس ایستاده‌اند. هر نفر یک شماره بلیط یکتا بین ‎$1$‎ و ‎$n$‎ دارد و در ابتدا افراد به ترتیب شماره بلیط‌شان در صف ایستاده‌اند. بعلت شلوغی ورزشگاه، مدت زیادی است که افراد در صف منتظرند و تعدادی مجبور می‌شوند جهت استفاده از سرویس بهداشتی از صف خارج شوند، ولی لزوماً به جای قبلی خود در صف باز نمی‌گردند بلکه یکی از دوستانشان را پیدا می‌کنند و دوست‌شان در یک حرکت غیر اخلاقی وی را به جلوی خود راه می‌دهد.

‎$M$‎ بار به ترتیب، یک نفر از صف خارج می‌شود و به صف باز می‌گردد (ورزشگاه ‎$1$‎ سرویس بهداشتی بیشتر ندارد). شما باید با توجه به وضعیت صف پس از بازگشت همه افراد، به ‎$Q$‎ سوال پاسخ دهید. هر سوال به یکی از دو صورت زیر است:

  • ‎P X‎: تماشاچی با شماره بلیط ‎$X$‎ چندمین نفر در صف است؟
  • ‎L X‎: شماره بلیط ‎$X$‎امین نفر در صف چند است؟

ورودی

  • در خط اول عدد ‎$2 \leq M \leq 50000$‎ می‌آید.
  • در ‎$M$‎ خط بعد، در هر خط دو عدد ‎$A$‎ و ‎$B$‎ بین ‎$1$‎ و ‎$10^9$‎ به معنی اینکه تماشاچی با شماره بلیط ‎$A$‎ از صف خارج شد و پس از بازگشت در جلوی تماشاچی با شماره بلیط ‎$B$‎ ایستاد.‎
  • در خط بعد عدد ‎$1 \leq Q \leq 50000$‎ و در ‎$Q$‎ خط بعد صورت سوال‌ها آمده است‎.

خروجی

‎$Q$‎ خط در خروجی بنویسید که خط ‎$i$‎ام جواب سوال ‎$i$‎ باشد.‎

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2‎
6 3‎
9 6‎
8
‎L 1‎
L 2‎
L 3‎
‎L 4‎
P 1
‎P 2‎
P 3‎
P 4
1‎
2‎
9‎
6‎
1‎
2‎
5‎
‎6
5‎
7 2‎
2 7‎
9 7‎
10 1‎
100005 99995‎
9
‎L 1
‎P 2
‎L 2‎
P 7‎
L 7‎
P 9‎
P 10‎
‎P 99999‎
‎L 100000‎
10‎
3‎
1‎
5‎
4‎
4‎
1‎
100000‎
‎99999‎

ابزار صفحه