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
#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;
}
# 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