Submission #136369

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136369	2019-07-25T07:55:26 Z	이온조(#3259)	Queue (CEOI06_queue)	C++14	50 / 100	99 ms	3696 KB

queue

#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

#	Verdict	Execution time	Memory	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