[Ceoi2006]Queue<\/p>\n
Time Limit:10000MS Memory Limit:65536K
Total Submit:17 Accepted:12
Case Time Limit:1000MS<\/p>\n
Description <\/strong><\/p>\n If you are an average football fan, you probably know that obtaining tickets for this year’s World Cup in Germany was an impossible task. Greedy organizers and football federations grabbed the majority or available tickets and divided them among sponsors, friends and family members. As a result, jet setters have flooded the venues, while die-hard fans sit at home enjoying the games between advertisements featuring crappy beer and sugar-free chewing gum. \u4e00\u5f00\u59cb\u5c06\u4e00\u5217\u4eba\u6309\u7f16\u53f7\u4ece1\u5f00\u59cb\u987a\u5e8f\u6392\u5217\uff0c\u7136\u540e\u8fdb\u884cN\u6b21\u64cd\u4f5c\uff0c\u6bcf\u6b21\u5c06\u7f16\u53f7\u4e3aA\u7684\u4eba\u62ff\u51fa\uff0c\u653e\u5728\u7f16\u53f7\u4e3aB\u7684\u4eba\u524d\u9762\uff0c\u6240\u6709\u64cd\u4f5c\u8fdb\u884c\u5b8c\u540e\u6709Q\u4e2a\u95ee\u9898\uff0c\u8be2\u95ee\u7f16\u53f7\u4e3aX\u7684\u4eba\u7684\u4f4d\u7f6e\uff0c\u6216\u8005\u8be2\u95ee\u5728X\u53f7\u4f4d\u7f6e\u4e0a\u7684\u4eba\u7684\u7f16\u53f7\u3002 <\/p>\n Input <\/strong><\/p>\n The first line of input contains an integer N(2 \u2264 N \u2264 50 000)- the total number of restroom visits. Output <\/strong><\/p>\n The output should consist of a total of Q lines. Grading Sample Input <\/strong><\/p>\n<\/p>\n Sample Output <\/strong><\/p>\n<\/p>\n Source 103154411000009999926 39 68L 1L 2L 3L 4P 1P 2P 3P 4Output12961256Input57 22 79 710 110005 99959L 1P 2L 2P 7L 7P 9P 10P 99999P 100000 <\/p>\n","protected":false},"excerpt":{"rendered":" [Ceoi2006]Queue Time Limit:10000MS Memory Limit:65536KTotal Submit:17 Accepted:12 Case Time Limit:1000MS Description If you are an average football fan, you probably know that obtaining tickets for this year’s World Cup in Germany was an impossible task. Greedy organizers and football federations grabbed the majority or available tickets and divided them among sponsors, friends and family members. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/274"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=274"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/274\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=274"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=274"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=274"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
A couple of tickets are left for the final game and a huge queue has formed in front of the ticker office. As fans were arriving, they were labeled with successive integers. The first person in queue was labeled with number one, the second with number two, etc.
Since the fans arrived the night before, they had to wait for a long time before the ticket counter was open and, naturally, some of them had to use the restroom. Each time a person needs to use the restroom, he\/she steps out of the queue and, and, after completing the task, steps back into the queue, though not necessarily at the same position as before. Since there is only one restroom available no person leaves the queue before the previous person has returned (hence, at any moment there is at most one person missing from the queue).
During the course of the night, a total of N restroom visits have occurred. Each visit is described by two positive integers A and B, denoting that the person labeled A stepped out of the queue and the stepped back into the queue immediately in front of the person labeled B. Now that all the visits have completed, the officials have to answer a series of questions. Each question is either of the form ‘P X’, asking for the position lf the person labeled X, or of the form ‘L X’, asking for the label of the person at position X.
The first person in queue is considered to be at position one, the second at position two, etc.
Write a program that, given the description of the visits and a number of questions, answers all of the questions. <\/p>\n
Each of the following N lines contains two different integers A and B (1 \u2264 A, B \u2264 109), describing one restroom visit. The nest line contains an integer Q (1 \u2264 Q \u2264 50 000) – the total number of questions.
Each of the following Q lines contains a single character (either the uppercase letter ‘P’ or the uppercase letter ‘L’) and an integer X (1\u2264 X \u2264109) , describing one question. <\/p>\n
The ith line or output should contain a single integer R – the answer to the ith question.
If the corresponding question is of the form ‘P Xi’ then R should be the final position of the person labeled Xi.
If the corresponding question is of the form ‘L Xi’ then R should be the label of the person at position Xi. <\/p>\n
Partial credit is awarded for incorrect solutions that correctly answer all questions of one type. If all questions of the form ‘P X’ are answered correctly or if all questions of the form ‘L X’ are answered correctly, you will receive 50% of the corresponding test case.
In order to receive partial credit, the output should be formatted according to the specifications. Therefore, even if you choose to answer only one type of questions, you should still produce output for all questions of the other type. <\/p>\n
\u989d\u3002\u3002\u3002\u8fd9\u9898\u5b9e\u9645\u4e0a\u53ea\u8981\u6ce8\u610f\u5230\u4e00\u79cd\u6280\u672f\u53eb\u5b9e\u65f6\u79bb\u6563\u5316\uff0c\u7531\u4e8e\u8303\u56f4\u5f88\u5927\u800cn\u5f88\u5c0f\uff0c\u5f88\u591a\u5757\u90fd\u662f\u8fde\u7eed\u7684\u3002\u3002\u90a3\u4e48\u4fe1\u606f\u53ef\u4ee5\u5ffd\u7565\uff0c\u53ea\u9700\u8981\u8bb0\u5f55\u4e00\u4e9b\u8f6c\u89d2\u5730\u65b9\u7684\u70b9\u524d\u9a71\u548c\u540e\u7ee7\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u7136\u540e\u4e00\u904d\u626b\u63cf\u8fc7\u53bb\u5c31\u53ef\u4ee5\u5f97\u51fa\u6240\u6709\u7684\u7b54\u6848\u4e86\u3002\u3002\u6211\u7684\u7a0b\u5e8f\u9b3c\u901f\u5230\u4e86\u6781\u70b9\u3002\u3002\u56e7\u554a\u3002\u3002
Code\uff1a
#include <vector><\/strong>
#include <algorithm>
#include <utility>
#include <cstdio>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define All(x) x.begin(),x.end()
const int inf=2e9,maxn=50000+10;
using namespace std;
map<int,int> Pre,Next;
int n,m,Ans[maxn];
int pre(int x){return Pre.count(x)?Pre[x]:x-1;}
int next(int x){return Next.count(x)?Next[x]:x+1;}
typedef pair<int,int> ii;
typedef vector<ii>::iterator it;
vector<ii> L,P;
void init()
{
scanf("%d",&n);int a,b;
rep(i,n)
{
scanf("%d%d",&a,&b);
Next[pre(a)]=next(a);
Pre[next(a)]=pre(a);
Next[pre(b)]=a;
Pre[a]=pre(b);
Next[a]=b;
Pre[b]=a;
}
Next[inf]=inf+1;
char c;scanf("%d",&m);
rep(i,m)
{
scanf(" %c %d",&c,&a);
if(c==’P’)P.pb(ii(a,i));
else L.pb(ii(a,i));
}
L.pb(ii(inf,m));P.pb(ii(inf,m));
sort(All(L));sort(All(P));
}
void Solve()
{
int now=0,Min,pos=0;
while(now<inf)
{
int a=Next.lower_bound(now)->first-now;
int b=lower_bound(All(L),ii(pos,0))->first-pos;
int c=lower_bound(All(P),ii(now,0))->first-now;
Min=a<?b<?c;
now+=Min;pos+=Min;
if(Min==b)
{
it l=lower_bound(All(L),ii(pos,0)),r=lower_bound(All(L),ii(pos+1,0));
for(it i=l;i!=r;i++)
Ans[i->second]=now;
}
if(Min==c)
{
it l=lower_bound(All(P),ii(now,0)),r=lower_bound(All(P),ii(now+1,0));
for(it i=l;i!=r;i++)
Ans[i->second]=pos;
}
now=next(now);
++pos;
}
rep(i,m)printf("%dn",Ans[i]);
}
int main()
{
init();Solve();
}<\/p>\n