Submission #348503

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348503	2021-01-15T05:27:09 Z	arnold518	Queue (CEOI06_queue)	C++14	72 / 100	503 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;
unordered_map<int, int> A;
map<int, int> B;

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;
	vector<pii> C;

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

	int now=0;
	while(1)
	{
		if(B.find(now)!=B.end())
		{
			C.push_back({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.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

queue.cpp: In function 'int main()':
queue.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
queue.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
queue.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
queue.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |   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	118 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	132 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Correct	2 ms	492 KB	Output is correct
5	Correct	23 ms	1260 KB	Output is correct
6	Correct	30 ms	2156 KB	Output is correct
7	Correct	41 ms	2668 KB	Output is correct
8	Correct	53 ms	4324 KB	Output is correct
9	Correct	54 ms	4452 KB	Output is correct
10	Correct	59 ms	4708 KB	Output is correct
11	Correct	150 ms	9992 KB	Output is correct
12	Correct	119 ms	7916 KB	Output is correct
13	Correct	155 ms	10120 KB	Output is correct
14	Correct	158 ms	10120 KB	Output is correct
15	Correct	155 ms	10120 KB	Output is correct
16	Correct	157 ms	10120 KB	Output is correct
17	Runtime error	154 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	331 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	366 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	503 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
21	Correct	124 ms	10120 KB	Output is correct
22	Correct	157 ms	11420 KB	Output is correct
23	Correct	222 ms	14204 KB	Output is correct
24	Correct	217 ms	14208 KB	Output is correct
25	Incorrect	188 ms	10632 KB	Output isn't correct