Submission #136244

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136244	2019-07-25T04:43:41 Z	임유진(#3261)	Queue (CEOI06_queue)	C++14	100 / 100	82 ms	7156 KB

queue

#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++) {
        ~~~^~~~~~~~~~~

Subtask #1

100.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	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