Submission #268626

#	Time	Username	Problem	Language	Result	Execution time	Memory
268626		stefantaga	Queue (CEOI06_queue)	C++14	100 / 100	606 ms	21148 KiB

queue

#include<bits/stdc++.h>
using namespace std;

const int N = 50005, inf = 1e9+7;

map<int, int> fr, bk, s[2];

int getfr (int I) {
	if(fr.find(I) == fr.end()) return I-1;
	return fr[I];
}

int getbk (int I) {
	if(bk.find(I) == bk.end()) return I+1;
	return bk[I];
}
char ch;
int i,poz,n,q,CT=1;
int main()
{
	#ifdef HOME
	ifstream cin("queue.in");
	ofstream cout("queue.out");
	#endif // HOME
	cin>>n;
	while(n--) {
		int A, B;
		cin>>A>>B;
		int AF = getfr(A), AB = getbk(A), BF = getfr(B);
		if(A == B || AB == B) continue;
		fr[AB] = AF;
		bk[AF] = AB;
		fr[A] = BF;
		bk[BF] = A;
		fr[B] = A;
		bk[A] = B;
		if(CT == A) CT = AB;
		if(CT == B) CT = A;
	}
	bk[inf] = inf;
	for(int i=CT,j=1;i<inf;) {
		auto it = *bk.lower_bound(i);
		int E = it.first;
		j += E-i;
		s[0][E] = j;
		s[1][j] = E;
        i = it.second;
		j++;
	}
	cin>>q;
	for (i=1;i<=q;i++)
    {

		cin>>ch>>poz;
		if (ch=='L')
        {
           auto it = *s[1].lower_bound(poz);
           cout<<it.second-it.first+poz<<'\n';
        }
        else
        {
            auto it = *s[0].lower_bound(poz);
            cout<<it.second-it.first+poz<<'\n';
        }
	}
}

• Subtask 1: 100 / 100