Submission #136349

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136349	2019-07-25T07:26:44 Z	이온조(#3259)	Queue (CEOI06_queue)	C++14	0 / 100	441 ms	14420 KB

queue

#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

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