Submission #348498

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348498	2021-01-15T05:23:39 Z	arnold518	Queue (CEOI06_queue)	C++14	72 / 100	1000 ms	65540 KB

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;
map<int, int> A, B, C;

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

int getB(int x)
{
	if(B.find(x)==B.end()) return x+1;
	return B[x];
}

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);
		B[p]=q;
		A[q]=p;
		A[a]=b;
		B[a]=r;
		B[b]=a;
		A[r]=a;
	}

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

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

	int now=0;
	while(1)
	{
		if(B.find(now)!=B.end())
		{
			C[now]=V.size();
			V.push_back({now, now});
			V2.push_back(V2.back()+1);
			now=B[now];
		}
		else
		{
			auto it=B.lower_bound(now);
			if(it==B.end())
			{
				C[INF]=V.size();
				V.push_back({now, INF});
				V2.push_back(V2.back()+INF-now+1);
				break;
			}
			else
			{
				C[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]);
	}
*/
	scanf("%d", &Q);
	for(int i=1; i<=Q; i++)
	{
		char c; int x;
		scanf(" %c%d", &c, &x);

		if(c=='P')
		{
			int it=C.lower_bound(x)->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

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

Subtask #1

72.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Runtime error	192 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	212 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Correct	3 ms	620 KB	Output is correct
5	Correct	26 ms	1536 KB	Output is correct
6	Correct	37 ms	2668 KB	Output is correct
7	Correct	48 ms	3432 KB	Output is correct
8	Correct	67 ms	5860 KB	Output is correct
9	Correct	76 ms	6244 KB	Output is correct
10	Correct	82 ms	6760 KB	Output is correct
11	Correct	253 ms	14436 KB	Output is correct
12	Correct	209 ms	10800 KB	Output is correct
13	Correct	249 ms	14488 KB	Output is correct
14	Correct	248 ms	14560 KB	Output is correct
15	Correct	244 ms	14560 KB	Output is correct
16	Correct	263 ms	14560 KB	Output is correct
17	Runtime error	252 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	845 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	946 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Execution timed out	1085 ms	54328 KB	Time limit exceeded
21	Correct	191 ms	14304 KB	Output is correct
22	Correct	245 ms	16480 KB	Output is correct
23	Correct	355 ms	20700 KB	Output is correct
24	Correct	340 ms	20308 KB	Output is correct
25	Incorrect	294 ms	14304 KB	Output isn't correct