Submission #136229

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136229	2019-07-25T04:15:52 Z	윤교준(#3260)	Queue (CEOI06_queue)	C++14	56 / 100	1000 ms	3440 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() {
	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];
		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	6 ms	1272 KB	Output is correct
5	Correct	26 ms	1912 KB	Output is correct
6	Correct	56 ms	2168 KB	Output is correct
7	Correct	145 ms	2420 KB	Output is correct
8	Correct	343 ms	2796 KB	Output is correct
9	Correct	404 ms	2924 KB	Output is correct
10	Correct	500 ms	3056 KB	Output is correct
11	Execution timed out	1075 ms	3184 KB	Time limit exceeded
12	Execution timed out	1081 ms	2928 KB	Time limit exceeded
13	Execution timed out	1063 ms	3192 KB	Time limit exceeded
14	Execution timed out	1052 ms	3176 KB	Time limit exceeded
15	Execution timed out	1060 ms	3148 KB	Time limit exceeded
16	Execution timed out	1084 ms	3184 KB	Time limit exceeded
17	Correct	25 ms	1912 KB	Output is correct
18	Correct	105 ms	2040 KB	Output is correct
19	Correct	208 ms	2296 KB	Output is correct
20	Correct	522 ms	2932 KB	Output is correct
21	Execution timed out	1076 ms	2896 KB	Time limit exceeded
22	Execution timed out	1060 ms	3184 KB	Time limit exceeded
23	Execution timed out	1076 ms	3440 KB	Time limit exceeded
24	Execution timed out	1065 ms	3440 KB	Time limit exceeded
25	Execution timed out	1065 ms	3184 KB	Time limit exceeded