Submission #136231

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136231	2019-07-25T04:19:08 Z	윤교준(#3260)	Queue (CEOI06_queue)	C++14	100 / 100	299 ms	6896 KB

queue

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

const int MAXN = 200005;
const int SQRN = 450;
const int MAXK = 50005;

struct BUK {
	int A[SQRN*2], n;

	void init() { n = 0; }
	int find(int x) {
		for(int i = n; i--;)
			if(A[i] == x) return i;
		return -1;
	}
	void pop(int i) {
		for(int j = i+1; j < n; j++) A[j-1] = A[j];
		n--;
	}
	void push(int i, int x) {
		for(int j = n-1; i <= j; j--) A[j+1] = A[j];
		A[i] = x;
		n++;
	}
} buk[SQRN];

vector<pii> LV;
int O[MAXN], C[MAXN], RO[MAXN];
int BI[MAXN];

vector<int> XV;
int A[MAXK], B[MAXK];

int N, K, Q, TN;

void merge() {
	int n = 0;
	for(int i = 0; i < SQRN; i++) {
		for(int j = 0; j < buk[i].n; j++)
			O[n++] = buk[i].A[j];
	}
}

int TV[MAXN];
void norm() {
	TN = 0;
	int n = 0;
	for(int i = 0; i < SQRN; i++) {
		for(int j = 0; j < buk[i].n; j++)
			TV[n++] = buk[i].A[j];
		buk[i].init();
	}
	for(int i = 0, s = 0, e; i < SQRN; i++) {
		e = s + SQRN - 1;
		if(n <= e) e = n-1;
		if(s > e) break;
		buk[i].n = e-s+1;
		for(int j = s; j <= e; j++) {
			buk[i].A[j-s] = TV[j];
			BI[TV[j]] = i;
		}
		s = e+1;
	}
}

void initBuk() {
	for(int i = 0, s = 0, e; i < SQRN; i++) {
		e = s + SQRN - 1;
		if(N <= e) e = N-1;
		if(s > e) return;
		buk[i].n = e-s+1;
		for(int j = s; j <= e; j++) {
			buk[i].A[j-s] = j;
			BI[j] = i;
		}
		s = e+1;
	}
}

void pop(int x) {
	TN++;
	if(SQRN == TN) norm();
	int i = BI[x], j = buk[i].find(x);
	j = buk[i].find(x);
	buk[i].pop(j);
}
void push(int x, int y) { // 'x' y
	TN++;
	if(SQRN == TN) norm();
	int i = BI[y], j = buk[i].find(y);
	buk[i].push(j, x);
	BI[x] = i;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> K;
	for(int i = 0; i < K; i++) {
		cin >> A[i] >> B[i];
		XV.eb(A[i]);
		XV.eb(B[i]);
	}
	sorv(XV); univ(XV);

	for(int i = 0, n = sz(XV); i < n; i++) {
		if(i && XV[i-1]+1 < XV[i]) LV.eb(XV[i-1]+1, XV[i]-1);
		if(!i && 1 < XV[i]) LV.eb(1, XV[i]-1);
		LV.eb(XV[i], XV[i]);
	}
	LV.eb(XV.back()+1, INF);
	N = sz(LV);

	initBuk();
	for(int i = 0, a, b; i < K; i++) {
		a = int(lower_bound(allv(LV), pii(A[i], A[i])) - LV.begin());
		b = int(lower_bound(allv(LV), pii(B[i], B[i])) - LV.begin());
		pop(a);
		push(a, b);
	}
	merge();

	C[0] = 1;
	for(int oi = 0, i; oi < N; oi++) {
		RO[O[oi]] = oi;
		i = O[oi];
		C[oi+1] = C[oi] + (LV[i].second - LV[i].first + 1);
	}

	cin >> Q;
	for(int a, i; Q--;) {
		char t; cin >> t >> a;
		if('L' == t) {
			i = int(upper_bound(C, C+N, a) - C) - 1;
			cout << LV[O[i]].first + (a-C[i]) << '\n';
		} else {
			i = int(upper_bound(allv(LV), pii(a, INF)) - LV.begin()) - 1;
			cout << C[RO[i]] + (a - LV[i].first) << '\n';
		}
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	380 KB	Output is correct
3	Correct	5 ms	2040 KB	Output is correct
4	Correct	5 ms	2040 KB	Output is correct
5	Correct	24 ms	2680 KB	Output is correct
6	Correct	28 ms	2964 KB	Output is correct
7	Correct	36 ms	3188 KB	Output is correct
8	Correct	47 ms	3696 KB	Output is correct
9	Correct	53 ms	3696 KB	Output is correct
10	Correct	55 ms	3924 KB	Output is correct
11	Correct	208 ms	5324 KB	Output is correct
12	Correct	190 ms	4720 KB	Output is correct
13	Correct	211 ms	5360 KB	Output is correct
14	Correct	212 ms	5360 KB	Output is correct
15	Correct	228 ms	5492 KB	Output is correct
16	Correct	216 ms	5360 KB	Output is correct
17	Correct	27 ms	2680 KB	Output is correct
18	Correct	42 ms	2872 KB	Output is correct
19	Correct	61 ms	3028 KB	Output is correct
20	Correct	103 ms	3576 KB	Output is correct
21	Correct	145 ms	5356 KB	Output is correct
22	Correct	207 ms	6000 KB	Output is correct
23	Correct	299 ms	6764 KB	Output is correct
24	Correct	288 ms	6896 KB	Output is correct
25	Correct	244 ms	5872 KB	Output is correct