Submission #348528

#	Time	Username	Problem	Language	Result	Execution time	Memory
348528		arnold518	Queue (CEOI06_queue)	C++14	8 / 100	90 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;
const int MOD = 2500007;

int N, Q;
pii A[MOD];
int B[MOD];

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

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

int main()
{
	scanf("%d", &N);
	for(int i=0; i<MOD; i++) A[i]=pii(-1, -1), B[i]=-1;
	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);
		A[p%MOD].second=q;
		A[q%MOD].first=p;
		A[a%MOD].first=b;
		A[a%MOD].second=r;
		A[b%MOD].second=a;
		A[r%MOD].first=a;

		B[p%MOD]=p;
		B[q%MOD]=q;
		B[a%MOD]=a;
		B[a%MOD]=a;
		B[b%MOD]=b;
		B[r%MOD]=r;

	}

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

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

	for(int i=0; i<MOD; i++)
	{
		if(B[i]!=-1) BB.push_back(pii(B[i], A[i].second));
	}

	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:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
queue.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
queue.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
queue.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |   scanf(" %c%d", &c, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 100