Submission #348493

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348493	2021-01-15T05:18:35 Z	arnold518	Queue (CEOI06_queue)	C++14	36 / 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;
			}
		}
	}

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

Subtask #1

36.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	364 KB	Partially correct
2	Runtime error	163 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	211 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Partially correct	3 ms	620 KB	Partially correct
5	Partially correct	26 ms	1388 KB	Partially correct
6	Partially correct	37 ms	2540 KB	Partially correct
7	Partially correct	49 ms	3304 KB	Partially correct
8	Partially correct	67 ms	5732 KB	Partially correct
9	Partially correct	78 ms	6116 KB	Partially correct
10	Partially correct	82 ms	6760 KB	Partially correct
11	Partially correct	245 ms	14460 KB	Partially correct
12	Partially correct	205 ms	10720 KB	Partially correct
13	Partially correct	240 ms	14304 KB	Partially correct
14	Partially correct	249 ms	14408 KB	Partially correct
15	Partially correct	246 ms	14432 KB	Partially correct
16	Partially correct	255 ms	14560 KB	Partially correct
17	Runtime error	247 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	851 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	953 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Execution timed out	1071 ms	54068 KB	Time limit exceeded
21	Partially correct	189 ms	14176 KB	Partially correct
22	Partially correct	247 ms	16480 KB	Partially correct
23	Partially correct	337 ms	20188 KB	Partially correct
24	Partially correct	332 ms	20192 KB	Partially correct
25	Incorrect	287 ms	14176 KB	Output isn't correct