답안 #348493

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348493 2021-01-15T05:18:35 Z arnold518 Queue (CEOI06_queue) C++14
36 / 100
1000 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;

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);
      |   ~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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