답안 #348529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348529 2021-01-15T06:13:42 Z arnold518 Queue (CEOI06_queue) C++14
8 / 100
93 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[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);
      |   ~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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)