Submission #485876

#	Time	Username	Problem	Language	Result	Execution time	Memory
485876		rainboy	OGLEDALA (COI15_ogledala)	C11	41 / 100	250 ms	35220 KiB

ogledala

#include <stdio.h>

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

long long ll[K], rr[K]; int 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(long long l, long long 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 long long aa[N];
	long long m;
	int n, q, i;
	long long a_, b_;

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

		scanf("%lld", &b), b--;
		if (b < n)
			printf("%lld\n", aa[b]);
		else {
			while (b_ < b) {
				i = pq_remove_first();
				a_ = (ll[i] + rr[i]) / 2;
				pq_add(ll[i], a_), pq_add(a_, rr[i]);
				b_++;
			}
			printf("%lld\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:57:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%lld%d%d", &m, &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ogledala.c:60:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%lld", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~
ogledala.c:69:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%lld", &b), b--;
      |   ^~~~~~~~~~~~~~~~~

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