Submission #348522

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348522	2021-01-15T06:03:09 Z	arnold518	Queue (CEOI06_queue)	C++14	72 / 100	267 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, 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<pii> BB;
	vector<int> V2;
	vector<pii> C;

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

	for(auto it : B)
	{
		BB.push_back(it);
	}

	A.clear();
	B.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;
			}
		}
	}
	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: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:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
queue.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |   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	109 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	117 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	1280 KB	Output is correct
6	Correct	31 ms	1772 KB	Output is correct
7	Correct	33 ms	2156 KB	Output is correct
8	Correct	42 ms	3560 KB	Output is correct
9	Correct	47 ms	3688 KB	Output is correct
10	Correct	50 ms	3564 KB	Output is correct
11	Correct	96 ms	8628 KB	Output is correct
12	Correct	66 ms	6532 KB	Output is correct
13	Correct	97 ms	8500 KB	Output is correct
14	Correct	101 ms	8500 KB	Output is correct
15	Correct	99 ms	8500 KB	Output is correct
16	Correct	104 ms	8500 KB	Output is correct
17	Runtime error	133 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	195 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	204 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	267 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
21	Correct	88 ms	8244 KB	Output is correct
22	Correct	109 ms	9140 KB	Output is correct
23	Correct	148 ms	11824 KB	Output is correct
24	Correct	158 ms	11824 KB	Output is correct
25	Incorrect	115 ms	9008 KB	Output isn't correct