Submission #136235

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136235	2019-07-25T04:26:19 Z	김세빈(#3258)	Queue (CEOI06_queue)	C++14	100 / 100	96 ms	5996 KB

queue

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

vector <pii> V;
int L[303030], R[303030];
int P[303030], Y[303030], Z[303030];
vector <int> X;
int n;

int main()
{
	char S[4];
	int q, i, j, x, y, s;
	
	scanf("%d", &n);
	
	X.push_back(0);
	
	for(i=0; i<n; i++){
		scanf("%d%d", &x, &y);
		X.push_back(x - 1); X.push_back(x); X.push_back(x + 1);
		X.push_back(y - 1); X.push_back(y);
		V.emplace_back(x, y);
	}
	
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	
	n = X.size(); X.push_back(2e9);
	
	for(i=0; i<n; i++){
		L[i] = i - 1; R[i] = i + 1;
	}
	
	for(pii &t: V){
		tie(x, y) = t;
		x = lower_bound(X.begin(), X.end(), x) - X.begin();
		y = lower_bound(X.begin(), X.end(), y) - X.begin();
		L[R[x]] = L[x]; R[L[x]] = R[x];
		L[x] = L[y]; R[x] = y;
		L[y] = x; R[L[x]] = x;
	}
	
	for(i=0, j=0, s=0; i<n; i=R[i], j++){
		P[j] = s; Y[j] = i; Z[i] = j;
		s += X[i + 1] - X[i];
	}
	
	scanf("%d", &q);
	
	for(; q--; ){
		scanf("%s%d", S, &x);
		
		if(*S == 'P'){
			y = lower_bound(X.begin(), X.end(), x + 1) - X.begin() - 1;
			printf("%d\n", P[Z[y]] + x - X[y]);
		}
		else{
			y = lower_bound(P, P + n, x + 1) - P - 1;
			printf("%d\n", X[Y[y]] + x - P[y]);
		}
	}
	
	return 0;
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  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", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
queue.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
queue.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d", S, &x);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	28 ms	944 KB	Output is correct
6	Correct	34 ms	1272 KB	Output is correct
7	Correct	34 ms	1524 KB	Output is correct
8	Correct	40 ms	2036 KB	Output is correct
9	Correct	42 ms	2164 KB	Output is correct
10	Correct	45 ms	2436 KB	Output is correct
11	Correct	64 ms	4584 KB	Output is correct
12	Correct	57 ms	3708 KB	Output is correct
13	Correct	66 ms	4584 KB	Output is correct
14	Correct	69 ms	4712 KB	Output is correct
15	Correct	69 ms	4588 KB	Output is correct
16	Correct	70 ms	4716 KB	Output is correct
17	Correct	25 ms	1392 KB	Output is correct
18	Correct	35 ms	1532 KB	Output is correct
19	Correct	51 ms	2024 KB	Output is correct
20	Correct	77 ms	3032 KB	Output is correct
21	Correct	59 ms	4076 KB	Output is correct
22	Correct	75 ms	4968 KB	Output is correct
23	Correct	95 ms	5996 KB	Output is correct
24	Correct	96 ms	5996 KB	Output is correct
25	Correct	89 ms	4584 KB	Output is correct