Submission #348529

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348529	2021-01-15T06:13:42 Z	arnold518	Queue (CEOI06_queue)	C++14	8 / 100	93 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;
const int MOD = 2500007;

int N, Q;
pii A[MOD];
int B[MOD];

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

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

int main()
{
	scanf("%d", &N);
	for(int i=0; i<MOD; i++) A[i]=pii(-1, -1), B[i]=-1;
	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);
		A[p%MOD].second=q;
		A[q%MOD].first=p;
		A[a%MOD].first=b;
		A[a%MOD].second=r;
		A[b%MOD].second=a;
		A[r%MOD].first=a;

		B[p%MOD]=p;
		B[q%MOD]=q;
		B[a%MOD]=a;
		B[b%MOD]=b;
		B[r%MOD]=r;

	}

	vector<pii> V;
	vector<pii> BB;
	vector<int> V2;
	vector<pii> C;

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

	for(int i=0; i<MOD; i++)
	{
		if(B[i]!=-1 && A[i].second!=-1) BB.push_back(pii(B[i], A[i].second));
	}

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

Subtask #1

8.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	29676 KB	Output is correct
2	Runtime error	89 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	93 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Runtime error	59 ms	60032 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	61 ms	59908 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	59 ms	59944 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Correct	55 ms	32484 KB	Output is correct
13	Runtime error	61 ms	60012 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	59 ms	59912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	60 ms	60012 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	60 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Runtime error	60 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	60 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Runtime error	60 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)