답안 #348528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348528 2021-01-15T06:12:44 Z arnold518 Queue (CEOI06_queue) C++14
8 / 100
90 ms 65540 KB
#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);
      |   ~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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)