Submission #348524

#	Time	Username	Problem	Language	Result	Execution time	Memory
348524		arnold518	Queue (CEOI06_queue)	C++14	72 / 100	283 ms	65540 KiB

queue

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e4;
const int INF = 1e9+100;

int N, Q;
unordered_map<int, pii> A;

int getA(int x)
{
	if(A.find(x)==A.end() || A[x].first==-1) return x-1;
	return A[x].first;
}

int getB(int x)
{
	if(A.find(x)==A.end() || A[x].second==-1) return x+1;
	return A[x].second;
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		int p=getA(a), q=getB(a), r=getA(b); swap(b, r);
		if(A.find(p)==A.end()) A[p]=pii(-1, -1);
		if(A.find(q)==A.end()) A[q]=pii(-1, -1);
		if(A.find(a)==A.end()) A[a]=pii(-1, -1);
		if(A.find(b)==A.end()) A[b]=pii(-1, -1);
		if(A.find(r)==A.end()) A[r]=pii(-1, -1);
		A[p].second=q;
		A[q].first=p;
		A[a].first=b;
		A[a].second=r;
		A[b].second=a;
		A[r].first=a;
	}

	vector<pii> V;
	vector<pii> BB;
	vector<int> V2;
	vector<pii> C;

	V.push_back({-1, -1});
	V2.push_back(0);

	for(auto it : A)
	{
		BB.push_back(pii(it.first, it.second.second));
	}

	A.clear();
	sort(BB.begin(), BB.end());

	int now=0;
	while(1)
	{
		auto it=lower_bound(BB.begin(), BB.end(), pii(now, 0));
		if(it!=BB.end() && it->first==now)
		{
			C.push_back({now, V.size()});
			V.push_back({now, now});
			V2.push_back(V2.back()+1);
			now=it->second;
		}
		else
		{
			if(it==BB.end())
			{
				C.push_back({INF, V.size()});
				V.push_back({now, INF});
				V2.push_back(V2.back()+INF-now+1);
				break;
			}
			else
			{
				C.push_back({it->first-1, V.size()});
				V.push_back({now, it->first-1});
				V2.push_back(V2.back()+it->first-now);
				now=it->first;
			}
		}
	}
/*
	for(int i=0; i<V.size(); i++)
	{
		printf("%d %d : %d\n", V[i].first, V[i].second, V2[i]);
	}
*/

	sort(C.begin(), C.end());

	scanf("%d", &Q);
	for(int i=1; i<=Q; i++)
	{
		char c; int x;
		scanf(" %c%d", &c, &x);

		if(c=='P')
		{
			int it=lower_bound(C.begin(), C.end(), pii(x, -2))->second;
			int ans=V2[it-1]+x-V[it].first;
			printf("%d\n", ans);
		}
		else
		{
			x++;
			int it=lower_bound(V2.begin(), V2.end(), x)-V2.begin();
			int ans=V[it].first+x-V2[it-1]-1;
			printf("%d\n", ans);
		}
	}
}

Compilation message (stderr)

queue.cpp: In function 'int main()':
queue.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
queue.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
queue.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
queue.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |   scanf(" %c%d", &c, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 72 / 100