oj.uz

Submission #136390

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

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

bool chk(vector<int> &T, int x) { return x == *lower_bound(S.begin(), S.end(), x); }

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

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

int getL(int x) { return x + geti(PR, x) - geti(XS, 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]);
	}
	PR.push_back(INF);
	// 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]});
		XS.push_back(P[i]);
	}
	X.push_back({INF, INF});
	XS.push_back(INF);
	sort(X.begin(), X.end());
	sort(XS.begin(), XS.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", getL(x));
		}
	}
	return 0;
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:31: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:33: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:78: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:80: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 376 KB Partially correct
4 Partially correct 3 ms 376 KB Partially correct
5 Partially correct 35 ms 1016 KB Partially correct
6 Partially correct 39 ms 1272 KB Partially correct
7 Partially correct 45 ms 1528 KB Partially correct
8 Partially correct 52 ms 1792 KB Partially correct
9 Partially correct 56 ms 1908 KB Partially correct
10 Partially correct 58 ms 1972 KB Partially correct
11 Partially correct 65 ms 3312 KB Partially correct
12 Partially correct 61 ms 3312 KB Partially correct
13 Partially correct 69 ms 3412 KB Partially correct
14 Partially correct 72 ms 3436 KB Partially correct
15 Partially correct 75 ms 3568 KB Partially correct
16 Partially correct 72 ms 3440 KB Partially correct
17 Partially correct 21 ms 1012 KB Partially correct
18 Partially correct 34 ms 1140 KB Partially correct
19 Partially correct 47 ms 1440 KB Partially correct
20 Partially correct 71 ms 1900 KB Partially correct
21 Partially correct 73 ms 3184 KB Partially correct
22 Partially correct 92 ms 4080 KB Partially correct
23 Partially correct 125 ms 4472 KB Partially correct
24 Partially correct 116 ms 4484 KB Partially correct
25 Partially correct 109 ms 4460 KB Partially correct