Submission #544766

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544766	2022-04-02T16:35:14 Z	rainboy	Queue (CEOI06_queue)	C	100 / 100	75 ms	5460 KB

queue

#include <stdio.h>

#define N	50000
#define N_	(N * 3 + 1)

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int aa[N_];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa[ii[j]] == aa[i_])
				j++;
			else if (aa[ii[j]] < aa[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int main() {
	static int ii[N_], aa_[N_], ll[N_], rr[N_], pp[N_], qu[N_];
	int n, n_, q, i, p, cnt;

	scanf("%d", &n);
	aa[0] = 1;
	for (i = 0; i < n; i++) {
		int a, b;

		scanf("%d%d", &a, &b);
		aa[i * 3 + 1] = a, aa[i * 3 + 2] = a + 1, aa[i * 3 + 3] = b;
	}
	for (i = 0; i <= n * 3; i++)
		ii[i] = i;
	sort(ii, 0, n * 3 + 1);
	for (i = 0, n_ = 0; i <= n * 3; i++) {
		int a = aa[ii[i]];

		aa[ii[i]] = n_;
		if (i + 1 == n * 3 || aa[ii[i + 1]] != a)
			aa_[n_++] = a;
	}
	for (i = 0; i < n_; i++)
		ll[i] = i - 1, rr[i] = i + 1;
	for (i = 0; i < n; i++) {
		int i_ = aa[i * 3 + 1], j_ = aa[i * 3 + 3], l = ll[i_], r = rr[i_];

		if (l >= 0)
			rr[l] = r;
		if (r < n_)
			ll[r] = l;
		l = ll[j_];
		rr[i_] = j_, ll[j_] = i_;
		if (l >= 0)
			rr[l] = i_;
		ll[i_] = l;
	}
	i = 0;
	while (ll[i] >= 0)
		i++;
	p = 1, cnt = 0;
	while (i < n_) {
		qu[cnt++] = i;
		pp[i] = p;
		p += aa_[i + 1] - aa_[i];
		i = rr[i];
	}
	scanf("%d", &q);
	while (q--) {
		static char s[2];
		int x, lower, upper;

		scanf("%s%d", s, &x);
		if (s[0] == 'P') {
			lower = 0, upper = n_;
			while (upper - lower > 1) {
				i = (lower + upper) / 2;
				if (aa_[i] <= x)
					lower = i;
				else
					upper = i;
			}
			i = lower;
			printf("%d\n", pp[i] + x - aa_[i]);
		} else {
			lower = 0, upper = n_;
			while (upper - lower > 1) {
				i = (lower + upper) / 2;
				if (pp[qu[i]] <= x)
					lower = i;
				else
					upper = i;
			}
			i = lower;
			printf("%d\n", aa_[qu[i]] + x - pp[qu[i]]);
		}
	}
	return 0;
}

Compilation message

queue.c: In function 'main':
queue.c:37:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
queue.c:42:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d%d", &a, &b);
      |   ^~~~~~~~~~~~~~~~~~~~~
queue.c:80:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
queue.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%s%d", s, &x);
      |   ^~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	22 ms	1484 KB	Output is correct
6	Correct	19 ms	1584 KB	Output is correct
7	Correct	24 ms	1876 KB	Output is correct
8	Correct	27 ms	2232 KB	Output is correct
9	Correct	31 ms	2324 KB	Output is correct
10	Correct	29 ms	2508 KB	Output is correct
11	Correct	36 ms	3788 KB	Output is correct
12	Correct	32 ms	3172 KB	Output is correct
13	Correct	39 ms	3968 KB	Output is correct
14	Correct	47 ms	4052 KB	Output is correct
15	Correct	51 ms	4064 KB	Output is correct
16	Correct	44 ms	4044 KB	Output is correct
17	Correct	14 ms	1516 KB	Output is correct
18	Correct	22 ms	1792 KB	Output is correct
19	Correct	42 ms	2476 KB	Output is correct
20	Correct	51 ms	3616 KB	Output is correct
21	Correct	36 ms	3532 KB	Output is correct
22	Correct	48 ms	4428 KB	Output is correct
23	Correct	75 ms	5392 KB	Output is correct
24	Correct	75 ms	5460 KB	Output is correct
25	Correct	61 ms	5008 KB	Output is correct