Submission #136230

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136230	2019-07-25T04:18:06 Z	윤교준(#3260)	Queue (CEOI06_queue)	C++14	88 / 100	284 ms	10092 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 = 100005;
const int SQRN = 330;
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

88.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	4 ms	1272 KB	Output is correct
4	Correct	5 ms	1272 KB	Output is correct
5	Correct	22 ms	1912 KB	Output is correct
6	Correct	27 ms	2168 KB	Output is correct
7	Correct	36 ms	2424 KB	Output is correct
8	Correct	46 ms	2928 KB	Output is correct
9	Correct	50 ms	3032 KB	Output is correct
10	Correct	56 ms	3184 KB	Output is correct
11	Correct	245 ms	4716 KB	Output is correct
12	Correct	210 ms	4080 KB	Output is correct
13	Correct	259 ms	4556 KB	Output is correct
14	Correct	251 ms	4564 KB	Output is correct
15	Correct	250 ms	4592 KB	Output is correct
16	Correct	264 ms	4592 KB	Output is correct
17	Correct	24 ms	1912 KB	Output is correct
18	Correct	38 ms	2040 KB	Output is correct
19	Correct	58 ms	2332 KB	Output is correct
20	Correct	92 ms	2840 KB	Output is correct
21	Correct	155 ms	4560 KB	Output is correct
22	Runtime error	50 ms	9456 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	109 ms	10092 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	107 ms	7892 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Correct	284 ms	5228 KB	Output is correct