Submission #348524

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348524	2021-01-15T06:07:59 Z	arnold518	Queue (CEOI06_queue)	C++14	72 / 100	283 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, pii> A;

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

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

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);
		if(A.find(p)==A.end()) A[p]=pii(-1, -1);
		if(A.find(q)==A.end()) A[q]=pii(-1, -1);
		if(A.find(a)==A.end()) A[a]=pii(-1, -1);
		if(A.find(b)==A.end()) A[b]=pii(-1, -1);
		if(A.find(r)==A.end()) A[r]=pii(-1, -1);
		A[p].second=q;
		A[q].first=p;
		A[a].first=b;
		A[a].second=r;
		A[b].second=a;
		A[r].first=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 : A)
	{
		BB.push_back(pii(it.first, it.second.second));
	}

	A.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;
			}
		}
	}
/*
	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:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
queue.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |   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	107 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	115 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	1132 KB	Output is correct
6	Correct	29 ms	1644 KB	Output is correct
7	Correct	37 ms	2280 KB	Output is correct
8	Correct	45 ms	3848 KB	Output is correct
9	Correct	48 ms	4100 KB	Output is correct
10	Correct	52 ms	3956 KB	Output is correct
11	Correct	90 ms	6472 KB	Output is correct
12	Correct	63 ms	6156 KB	Output is correct
13	Correct	92 ms	6544 KB	Output is correct
14	Correct	99 ms	6668 KB	Output is correct
15	Correct	93 ms	6544 KB	Output is correct
16	Correct	99 ms	6544 KB	Output is correct
17	Runtime error	135 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	199 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	217 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	283 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
21	Correct	86 ms	6668 KB	Output is correct
22	Correct	112 ms	8884 KB	Output is correct
23	Correct	147 ms	11696 KB	Output is correct
24	Correct	152 ms	11696 KB	Output is correct
25	Incorrect	99 ms	7692 KB	Output isn't correct