Submission #348528

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348528	2021-01-15T06:12:44 Z	arnold518	Queue (CEOI06_queue)	C++14	8 / 100	90 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[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) 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:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
queue.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |   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	87 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	90 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	60 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	60 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	59 ms	59884 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	60 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	62 ms	60012 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	61 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Correct	55 ms	33376 KB	Output is correct
13	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	62 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	61 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	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	59 ms	59884 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	61 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Runtime error	60 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	60 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Runtime error	59 ms	59884 KB	Execution killed with signal 11 (could be triggered by violating memory limits)