oj.uz

답안 #136369

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

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

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(); }

inline int getp(int x) { return x + geti(NW, x) - geti(PR, x); }

// void showpos() {
// 	printf("showing position\n");
// 	for(auto& it: P) printf("position of %d: %d\n", it.first, it.second);
// 	puts("\n\n");
// 	puts("relative order:");
// 	int now = R[0];
// 	while(now != INF) {
// 		printf("%d\n", now);
// 		now = R[now];
// 	}
// 	puts("\n\n");
// }

int main() {
	
	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] = 1; L[K+1] = K;
	for(int i=1; i<=K; i++) {
		R[i] = i+1, L[i] = i-1, P[i] = i;
		PR.push_back(S[i]);
	}
	// showpos();
	for(int i=1; i<=N; i++) {
		int ai = geti(S, A[i]), bi = geti(S, B[i]);
		int l = L[ai], r = R[ai];
		R[l] = r; L[r] = l;
		R[ai] = bi; L[ai] = L[bi];
		R[L[bi]] = ai; L[bi] = ai;
		P[ai] = P[bi];
		// showpos();
	}
	int now = R[0], cnt = 1;
	while(now != K+1) {
		// printf("now: %d\n", now);
		// printf("position: %d\n\n", P[now]);
		NW.push_back(S[P[now]]);
		if(!M[P[now]]) M[P[now]] = cnt;
		O[now] = cnt;
		// printf("position: %d\n\n", P[now]);
		now = R[now];
		++cnt;
	}
	for(int i=1; i<=K; i++) P[i] = getp(S[P[i]]) + O[i] - M[P[i]];
	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[geti(S, x)]);
			else printf("%d\n", getp(x));
		}
		if(t == 'L') {
			printf("%d\n", 123456789);
		}
	}
	return 0;
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:29: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:31: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:65: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:67: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
50.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 376 KB Partially correct
2 Partially correct 2 ms 376 KB Partially correct
3 Partially correct 3 ms 376 KB Partially correct
4 Partially correct 3 ms 376 KB Partially correct
5 Partially correct 27 ms 920 KB Partially correct
6 Partially correct 38 ms 1144 KB Partially correct
7 Partially correct 32 ms 1272 KB Partially correct
8 Partially correct 31 ms 1528 KB Partially correct
9 Partially correct 41 ms 1656 KB Partially correct
10 Partially correct 44 ms 1784 KB Partially correct
11 Partially correct 57 ms 2544 KB Partially correct
12 Partially correct 53 ms 2560 KB Partially correct
13 Partially correct 61 ms 2672 KB Partially correct
14 Partially correct 62 ms 2668 KB Partially correct
15 Partially correct 63 ms 2672 KB Partially correct
16 Partially correct 65 ms 2668 KB Partially correct
17 Partially correct 20 ms 1012 KB Partially correct
18 Partially correct 27 ms 1140 KB Partially correct
19 Partially correct 41 ms 1396 KB Partially correct
20 Partially correct 58 ms 1772 KB Partially correct
21 Partially correct 53 ms 2420 KB Partially correct
22 Partially correct 76 ms 3316 KB Partially correct
23 Partially correct 99 ms 3568 KB Partially correct
24 Partially correct 96 ms 3696 KB Partially correct
25 Partially correct 87 ms 3692 KB Partially correct