oj.uz

Submission #695068

# Submission time Handle Problem Language Result Execution time Memory
695068 2023-02-04T17:18:37 Z rainboy Sushi (JOI16_sushi) C
15 / 100
 4232 ms 5940 KB 
#include <stdio.h>
#include <string.h>

#define N	400000
#define K	633	/* K = ceil(sqrt(N)) */
#define M	((N + K - 1) / K)

int min(int a, int b) { return a < b ? a : b; }

int aa[N], aa_[N], n; char upd[N];
int iq[M][K + 1], pq[N], cnt[M], h1;

int lt(int i, int j) { return aa[i] > aa[j]; }

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

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

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

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

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

int pq_first() {
	return iq[h1][1];
}

void pq_add(int i) {
	pq[i] = ++cnt[h1], pq_up(i);
}

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

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

void build(int h) {
	int l = h * K, r = min((h + 1) * K, n) - 1, i, p;

	h1 = h;
	memset(pq + l, 0, (r - l + 1) * sizeof *pq), cnt[h1] = 0;
	for (i = l; i <= r; i++)
		iq[h1][pq[i] = ++cnt[h1]] = i;
	for (p = cnt[h1] / 2; p > 0; p--)
		pq_dn(iq[h1][p]);
}

void refresh(int h) {
	int l = h * K, r = min((h + 1) * K, n) - 1, i, j;

	h1 = h;
	memset(pq + l, 0, (r - l + 1) * sizeof *pq), cnt[h1] = 0;
	for (i = l; i <= r; i++)
		if (upd[i])
			pq_add(i);
	for (i = l; i <= r; i++) {
		if (!upd[i])
			pq_add(i);
		j = pq_remove_first();
		aa_[i] = aa[j];
	}
	memcpy(aa + l, aa_ + l, (r - l + 1) * sizeof *aa);
	memset(upd + l, 0, (r - l + 1) * sizeof *upd);
	build(h);
}

int walk(int h, int l, int r, int a) {
	int i, tmp;

	for (i = l; i <= r; i++)
		if (a < aa[i])
			tmp = a, a = aa[i], aa[i] = tmp;
	build(h);
	return a;
}

int run(int h, int a) {
	int i, tmp;

	h1 = h, i = pq_first();
	if (a < aa[i])
		tmp = a, a = aa[i], aa[i] = tmp, upd[i] = 1, pq_dn(i);
	return a;
}

int main() {
	int q, h, i;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (h = 0; h * K < n; h++)
		build(h);
	while (q--) {
		int s, t, hs, ht, a;

		scanf("%d%d%d", &s, &t, &a), s--, t--, hs = s / K, ht = t / K;
		if (s <= t) {
			if (hs == ht) {
				refresh(hs);
				a = walk(hs, s, t, a);
			} else {
				refresh(hs), refresh(ht);
				a = walk(hs, s, (hs + 1) * K - 1, a);
				for (h = hs + 1; h < ht; h++)
					a = run(h, a);
				a = walk(ht, ht * K, t, a);
			}
		} else {
			if (hs == ht)
				refresh(hs);
			else
				refresh(hs), refresh(ht);
			a = walk(hs, s, min((hs + 1) * K, n) - 1, a);
			for (h = hs + 1; h * K < n; h++)
				a = run(h, a);
			for (h = 0; h < ht; h++)
				a = run(h, a);
			a = walk(ht, ht * K, t, a);
		}
		printf("%d\n", a);
	}
	return 0;
}

Compilation message

sushi.c: In function 'main':
sushi.c:104:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
sushi.c:106:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
sushi.c:112:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   scanf("%d%d%d", &s, &t, &a), s--, t--, hs = s / K, ht = t / K;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3415 ms 5800 KB Output is correct
2 Correct 3340 ms 5660 KB Output is correct
3 Correct 1066 ms 5240 KB Output is correct
4 Correct 3570 ms 5768 KB Output is correct
5 Correct 3999 ms 5940 KB Output is correct
6 Correct 4226 ms 5920 KB Output is correct
7 Correct 4194 ms 5840 KB Output is correct
8 Correct 4206 ms 5876 KB Output is correct
9 Correct 1016 ms 5144 KB Output is correct
10 Correct 3846 ms 5652 KB Output is correct
11 Correct 1120 ms 4984 KB Output is correct
12 Correct 3903 ms 5748 KB Output is correct
13 Correct 3431 ms 5908 KB Output is correct
14 Correct 3361 ms 5780 KB Output is correct
15 Correct 1081 ms 5268 KB Output is correct
16 Correct 3344 ms 5680 KB Output is correct
17 Correct 3830 ms 5776 KB Output is correct
18 Correct 4232 ms 5728 KB Output is correct
19 Correct 4137 ms 5732 KB Output is correct
20 Correct 4199 ms 5636 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -