Submission #485875

#	Time	Username	Problem	Language	Result	Execution time	Memory
485875		rainboy	OGLEDALA (COI15_ogledala)	C11	19 / 100	205 ms	24516 KiB

ogledala

#include <stdio.h>

#define N	100000
#define B	300000
#define K	(N + 1 + B * 2)

int ll[K], rr[K], k;

int pq[K], iq[1 + K], cnt;

int lt(int i, int j) {
	return rr[i] - ll[i] > rr[j] - ll[j] || rr[i] - ll[i] == rr[j] - ll[j] && ll[i] < ll[j];
}

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add(int l, int r) {
	int i = k++;

	ll[i] = l, rr[i] = r;
	pq[i] = ++cnt, pq_up(i);
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];

	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int main() {
	static int aa[N];
	long long m, n, q;
	int i, a_, b_;

	scanf("%lld%lld%lld", &m, &n, &q);
	a_ = 0;
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		pq_add(a_, aa[i]);
		a_ = aa[i];
	}
	pq_add(a_, m + 1);
	b_ = n - 1, a_ = -1;
	while (q--) {
		int b;

		scanf("%d", &b), b--;
		if (b < n)
			printf("%d\n", aa[b]);
		else {
			while (b_ < b) {
				int i = pq_remove_first();

				a_ = (ll[i] + rr[i]) / 2;
				pq_add(ll[i], a_), pq_add(a_, rr[i]);
				b_++;
			}
			printf("%d\n", a_);
		}
	}
	return 0;
}

Compilation message (stderr)

ogledala.c: In function 'lt':
ogledala.c:12:73: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   12 |  return rr[i] - ll[i] > rr[j] - ll[j] || rr[i] - ll[i] == rr[j] - ll[j] && ll[i] < ll[j];
      |                                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
ogledala.c: In function 'main':
ogledala.c:56:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%lld%lld%lld", &m, &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ogledala.c:59:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
ogledala.c:68:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d", &b), b--;
      |   ^~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59