Submission #136226

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136226	2019-07-25T04:14:49 Z	윤교준(#3260)	Queue (CEOI06_queue)	C++14	56 / 100	1000 ms	3568 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];

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() {
	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];
		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;
		s = e+1;
	}
}

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

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

56.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	27 ms	1812 KB	Output is correct
6	Correct	57 ms	2208 KB	Output is correct
7	Correct	139 ms	2420 KB	Output is correct
8	Correct	342 ms	2800 KB	Output is correct
9	Correct	406 ms	2924 KB	Output is correct
10	Correct	507 ms	3184 KB	Output is correct
11	Execution timed out	1079 ms	3184 KB	Time limit exceeded
12	Execution timed out	1084 ms	2928 KB	Time limit exceeded
13	Execution timed out	1074 ms	3180 KB	Time limit exceeded
14	Execution timed out	1071 ms	3180 KB	Time limit exceeded
15	Execution timed out	1080 ms	3184 KB	Time limit exceeded
16	Execution timed out	1079 ms	3056 KB	Time limit exceeded
17	Correct	25 ms	1912 KB	Output is correct
18	Correct	120 ms	1996 KB	Output is correct
19	Correct	209 ms	2272 KB	Output is correct
20	Correct	521 ms	2804 KB	Output is correct
21	Execution timed out	1071 ms	2924 KB	Time limit exceeded
22	Execution timed out	1075 ms	3184 KB	Time limit exceeded
23	Execution timed out	1062 ms	3568 KB	Time limit exceeded
24	Execution timed out	1076 ms	3444 KB	Time limit exceeded
25	Execution timed out	1063 ms	3180 KB	Time limit exceeded