Submission #348505

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348505	2021-01-15T05:28:18 Z	arnold518	Queue (CEOI06_queue)	C++14	72 / 100	505 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);

	A.clear();

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

Subtask #1

72.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Runtime error	121 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	134 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	35 ms	2156 KB	Output is correct
7	Correct	39 ms	2668 KB	Output is correct
8	Correct	51 ms	4196 KB	Output is correct
9	Correct	57 ms	4452 KB	Output is correct
10	Correct	60 ms	4708 KB	Output is correct
11	Correct	155 ms	9992 KB	Output is correct
12	Correct	140 ms	7916 KB	Output is correct
13	Correct	175 ms	10120 KB	Output is correct
14	Correct	164 ms	10152 KB	Output is correct
15	Correct	166 ms	10416 KB	Output is correct
16	Correct	162 ms	10248 KB	Output is correct
17	Runtime error	152 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	328 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	368 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	505 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
21	Correct	128 ms	9992 KB	Output is correct
22	Correct	166 ms	11400 KB	Output is correct
23	Correct	247 ms	14160 KB	Output is correct
24	Correct	225 ms	14080 KB	Output is correct
25	Incorrect	186 ms	10792 KB	Output isn't correct