oj.uz

Submission #695063

# Submission time Handle Problem Language Result Execution time Memory
695063 2023-02-04T17:16:17 Z rainboy Sushi (JOI16_sushi) C
15 / 100
 4074 ms 5996 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);
}

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:103:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
sushi.c:105:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
sushi.c:111:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   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 60 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 3206 ms 5728 KB Output is correct
2 Correct 3183 ms 5636 KB Output is correct
3 Correct 891 ms 4988 KB Output is correct
4 Correct 3184 ms 5644 KB Output is correct
5 Correct 3544 ms 5788 KB Output is correct
6 Correct 4024 ms 5740 KB Output is correct
7 Correct 4011 ms 5628 KB Output is correct
8 Correct 3979 ms 5568 KB Output is correct
9 Correct 847 ms 5032 KB Output is correct
10 Correct 3641 ms 5512 KB Output is correct
11 Correct 854 ms 5256 KB Output is correct
12 Correct 3497 ms 5760 KB Output is correct
13 Correct 3139 ms 5724 KB Output is correct
14 Correct 3052 ms 5872 KB Output is correct
15 Correct 832 ms 5128 KB Output is correct
16 Correct 3000 ms 5996 KB Output is correct
17 Correct 3477 ms 5828 KB Output is correct
18 Correct 3911 ms 5884 KB Output is correct
19 Correct 3854 ms 5876 KB Output is correct
20 Correct 4074 ms 5704 KB Output is correct

Subtask #3
0 / 80.0

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