oj.uz

Submission #485876

# Submission time Handle Problem Language Result Execution time Memory
485876 2021-11-09T15:33:59 Z rainboy OGLEDALA (COI15_ogledala) C
41 / 100
 250 ms 35220 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 57 ms 4904 KB Output is correct
4 Correct 36 ms 3976 KB Output is correct
5 Correct 87 ms 12632 KB Output is correct
6 Correct 80 ms 12612 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 13168 KB Output is correct
2 Correct 55 ms 13228 KB Output is correct
3 Correct 128 ms 13208 KB Output is correct
4 Correct 99 ms 14404 KB Output is correct
5 Correct 101 ms 15556 KB Output is correct
6 Correct 134 ms 15576 KB Output is correct

Subtask #3
0 / 59.0

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