답안 #136244

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136244 2019-07-25T04:43:41 Z 임유진(#3261) Queue (CEOI06_queue) C++14
100 / 100
82 ms 7156 KB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;
const int INF = 1 << 30;

#define fi first
#define se second

typedef pair<int, int> pii;

struct NOD {
	NOD *l, *r;
	int s, e;

	NOD(int S = 0, int E = 0) {
		s = S;
		e = E;
	}
} *nil;

NOD *per[2 * MAXN], *head, *tail;
int A[MAXN], B[MAXN], D[MAXN];
char C[MAXN];
int ps[2 * MAXN], pn;
vector<pii> lq, pq;
int ans[MAXN];

void pushback(NOD *n) {
	n -> l = tail;
	tail -> r = n;
	tail = n;
	tail -> r = nil;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q;

	cin >> N;
	for(int i = 0; i < N; i++) cin >> A[i] >> B[i];
	cin >> Q;
	for(int i = 0; i < Q; i++) cin >> C[i] >> D[i];

	for(int i = 0; i < N; i++) {
		ps[2 * i] = A[i];
		ps[2 * i + 1] = B[i];
	}
	sort(ps, ps + 2 * N);
	pn = unique(ps, ps + 2 * N) - ps;
	//printf("pn = %d\n", pn);
	//for(int i = 0; i < pn; i++) printf("%d ", ps[i]);
	head = tail = new NOD(1, ps[0] - 1);
	nil = new NOD();
	tail -> r = nil;
	for(int i = 0; i < pn; i++) {
		per[i] = new NOD(ps[i], ps[i]);
		pushback(per[i]);
		if(i != pn - 1) pushback(new NOD(ps[i] + 1, ps[i + 1] - 1));
	}
	pushback(new NOD(ps[pn - 1] + 1, INF));
	//for(NOD *np = head; np != nil; np = np -> r) printf("[%d %d] ", np -> s, np -> e);
	//printf("\n");

	for(int i = 0; i < N; i++) {
		NOD *x = per[lower_bound(ps, ps + pn, A[i]) - ps], *y = per[lower_bound(ps, ps + pn, B[i]) - ps];
		//printf("x = %d, y = %d\n", x->s, y->s);
		x->r->l = x->l;
		x->l->r = x->r;
		x->l = y->l;
		x->r = y;
		y->l->r = x;
		y->l = x;
	}

	//for(NOD *np = head; np != nil; np = np -> r) printf("[%d %d] ", np -> s, np -> e);
	//printf("\n");

	for(int i = 0; i < Q; i++) {
		if(C[i] == 'L') lq.push_back(make_pair(D[i], i));
		else pq.push_back(make_pair(D[i], i));
	}
	sort(lq.begin(), lq.end());
	sort(pq.begin(), pq.end());

	int cnt = 0;
	NOD *np = head;
	for(auto a : lq) {
		//printf("lq[] = (%d, %d)\n", a.fi, a.se);
		while(cnt + np->e - np->s + 1 < a.fi) {
			cnt += np->e - np->s + 1;
			np = np->r;
		}
		//printf("cnt = %d, np = [%d %d]\n", cnt, np->s, np->e);
		ans[a.se] = np->s + a.fi - cnt - 1;
	}

	cnt = 0;
	for(np = head; np != nil; cnt += np->e - np->s + 1, np = np->r) {
		int lb = lower_bound(pq.begin(), pq.end(), make_pair(np->s, 0)) - pq.begin();
		//printf("np = [%d %d], cnt = %d, lb = %d\n", np->s, np->e, cnt, lb);
		for(;lb < pq.size() && pq[lb].fi <= np->e; lb++) {
			ans[pq[lb].se] = cnt + pq[lb].fi - np->s + 1;
		}
	}

	for(int i = 0; i < Q; i++) cout << ans[i] << "\n";
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:102:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;lb < pq.size() && pq[lb].fi <= np->e; lb++) {
        ~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 21 ms 2164 KB Output is correct
6 Correct 25 ms 2288 KB Output is correct
7 Correct 29 ms 2604 KB Output is correct
8 Correct 31 ms 3192 KB Output is correct
9 Correct 33 ms 3256 KB Output is correct
10 Correct 35 ms 3340 KB Output is correct
11 Correct 50 ms 4216 KB Output is correct
12 Correct 52 ms 4344 KB Output is correct
13 Correct 54 ms 4472 KB Output is correct
14 Correct 59 ms 4672 KB Output is correct
15 Correct 55 ms 4600 KB Output is correct
16 Correct 58 ms 4728 KB Output is correct
17 Correct 19 ms 1400 KB Output is correct
18 Correct 26 ms 1796 KB Output is correct
19 Correct 37 ms 2336 KB Output is correct
20 Correct 55 ms 3188 KB Output is correct
21 Correct 47 ms 4852 KB Output is correct
22 Correct 65 ms 6044 KB Output is correct
23 Correct 81 ms 7156 KB Output is correct
24 Correct 82 ms 7128 KB Output is correct
25 Correct 79 ms 7124 KB Output is correct