oj.uz

답안 #136349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136349 2019-07-25T07:26:44 Z 이온조(#3259) Queue (CEOI06_queue) C++14
0 / 100
 441 ms 14420 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 2e9;
vector<int> S;
int A[50009], B[50009];
map<int, int> L, R, P, O;

inline bool chk(int x) { return x == *lower_bound(S.begin(), S.end(), x); }

inline int geti(vector<int> &T, int x) { return lower_bound(T.begin(), T.end(), x) - T.begin(); }

void showpos() {
	printf("showing position\n");
	for(auto& it: P) printf("position of %d: %d\n", it.first, it.second);
	puts("\n\n");
}

int main() {
	vector<int> PR, NW;
	int N; scanf("%d",&N);
	for(int i=1; i<=N; i++) {
		scanf("%d%d", &A[i], &B[i]);
		S.push_back(A[i]);
		S.push_back(B[i]);
	}
	S.push_back(0); S.push_back(INF);
	sort(S.begin(), S.end()); S.resize(unique(S.begin(), S.end()) - S.begin());
	int K = S.size() - 2;
	R[0] = S[1]; L[INF] = S[K];
	for(int i=1; i<=K; i++) {
		R[S[i]] = S[i+1], L[S[i]] = S[i-1], P[S[i]] = S[i], O[S[i]] = i;
		PR.push_back(S[i]);
	}
	// showpos();
	for(int i=1; i<=N; i++) {
		int l = L[A[i]], r = R[A[i]];
		R[l] = r; L[r] = l;
		R[A[i]] = B[i]; L[A[i]] = L[B[i]];
		R[L[B[i]]] = A[i]; L[B[i]] = A[i];
		P[A[i]] = P[B[i]];

	}
	int now = R[0], cnt = 1;
	while(now != INF) {
		// printf("now: %d\n", now);
		// printf("position: %d\n\n", P[now]);
		NW.push_back(P[now]);
		P[now] += cnt - O[now];
		// printf("position: %d\n\n", P[now]);
		now = R[now];
		++cnt;
	}
	int Q; scanf("%d",&Q);
	while(Q--) {
		char t; int x; scanf(" %c%d",&t,&x);
		if(t == 'P') {
			if(chk(x)) printf("%d\n", P[x]);
			else printf("%d\n", x + geti(NW, x) - geti(PR, x));
		}
		if(t == 'L') {
			printf("%d\n", 123456789);
		}
	}
	return 0;
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d",&N);
         ~~~~~^~~~~~~~~
queue.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
queue.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int Q; scanf("%d",&Q);
         ~~~~~^~~~~~~~~
queue.cpp:56:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char t; int x; scanf(" %c%d",&t,&x);
                  ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Incorrect 5 ms 504 KB Output isn't correct
5 Incorrect 31 ms 1276 KB Output isn't correct
6 Incorrect 49 ms 2040 KB Output isn't correct
7 Incorrect 61 ms 2936 KB Output isn't correct
8 Incorrect 80 ms 4344 KB Output isn't correct
9 Incorrect 101 ms 4728 KB Output isn't correct
10 Incorrect 115 ms 5112 KB Output isn't correct
11 Incorrect 322 ms 9840 KB Output isn't correct
12 Incorrect 316 ms 9864 KB Output isn't correct
13 Incorrect 360 ms 10008 KB Output isn't correct
14 Incorrect 338 ms 9992 KB Output isn't correct
15 Incorrect 355 ms 9916 KB Output isn't correct
16 Incorrect 326 ms 9936 KB Output isn't correct
17 Incorrect 29 ms 1012 KB Output isn't correct
18 Incorrect 51 ms 1332 KB Output isn't correct
19 Incorrect 87 ms 1780 KB Output isn't correct
20 Incorrect 147 ms 2632 KB Output isn't correct
21 Incorrect 256 ms 10164 KB Output isn't correct
22 Incorrect 343 ms 12500 KB Output isn't correct
23 Incorrect 437 ms 14324 KB Output isn't correct
24 Incorrect 441 ms 14420 KB Output isn't correct
25 Incorrect 441 ms 14304 KB Output isn't correct