oj.uz

Submission #136375

# Submission time Handle Problem Language Result Execution time Memory
136375 2019-07-25T08:00:49 Z 이온조(#3259) Queue (CEOI06_queue) C++14
52 / 100
 111 ms 4480 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

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(vector<int> &T, 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;
	}
	vector<pii> X;
	for(int i=1; i<=K; i++) {
		P[i] = getp(S[P[i]]) + O[i] - M[P[i]];
		X.push_back({P[i], S[i]});
	}
	X.push_back({INF, INF});
	sort(X.begin(), X.end());
	int Q; scanf("%d",&Q);
	while(Q--) {
		char t; int x; scanf(" %c%d",&t,&x);
		if(t == 'P') {
			if(chk(S, x)) printf("%d\n", P[geti(S, x)]);
			else printf("%d\n", getp(x));
		}
		if(t == 'L') {
			int a, b; tie(a, b) = *lower_bound(X.begin(), X.end(), (pii){x, -INF});
			if(a == x) printf("%d\n", b);
			else printf("%d\n", 2*x - getp(x));
		}
	}
	return 0;
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:30: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:32: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:72: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:74: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
52.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Partially correct 2 ms 380 KB Partially correct
3 Partially correct 3 ms 380 KB Partially correct
4 Partially correct 3 ms 376 KB Partially correct
5 Partially correct 36 ms 1016 KB Partially correct
6 Partially correct 39 ms 1144 KB Partially correct
7 Partially correct 43 ms 1528 KB Partially correct
8 Partially correct 52 ms 1656 KB Partially correct
9 Partially correct 54 ms 1880 KB Partially correct
10 Partially correct 57 ms 1908 KB Partially correct
11 Partially correct 62 ms 3184 KB Partially correct
12 Partially correct 58 ms 3228 KB Partially correct
13 Partially correct 70 ms 3180 KB Partially correct
14 Partially correct 69 ms 3308 KB Partially correct
15 Partially correct 73 ms 3292 KB Partially correct
16 Partially correct 70 ms 3308 KB Partially correct
17 Partially correct 21 ms 1012 KB Partially correct
18 Partially correct 33 ms 1140 KB Partially correct
19 Partially correct 47 ms 1396 KB Partially correct
20 Partially correct 70 ms 1904 KB Partially correct
21 Partially correct 73 ms 2800 KB Partially correct
22 Partially correct 89 ms 3892 KB Partially correct
23 Partially correct 110 ms 4480 KB Partially correct
24 Partially correct 111 ms 4444 KB Partially correct
25 Partially correct 103 ms 4336 KB Partially correct