oj.uz

Submission #485875

# Submission time Handle Problem Language Result Execution time Memory
485875 2021-11-09T15:32:51 Z rainboy OGLEDALA (COI15_ogledala) C
19 / 100
 205 ms 24516 KB 
#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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 35 ms 3908 KB Output is correct
4 Correct 30 ms 3284 KB Output is correct
5 Correct 81 ms 9556 KB Output is correct
6 Correct 79 ms 9668 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 8516 KB Output is correct
2 Correct 50 ms 8508 KB Output is correct
3 Incorrect 97 ms 10648 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Runtime error 205 ms 24516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -