oj.uz

Submission #645720

# Submission time Handle Problem Language Result Execution time Memory
645720 2022-09-27T17:53:56 Z rainboy Fish 2 (JOI22_fish2) C
43 / 100
 4000 ms 7200 KB 
#include <stdio.h>
#include <string.h>

#define N	100000
#define N_	(1 << 17)	/* N_ = pow2(ceil(log2(N + 1))) */
#define INF	0x3f3f3f3f
#define LG	30

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

int aa[N];
long long st1[N_ * 2]; int st2[N_ * 2], kk2[N_ * 2], lz2[N_], h_, n_;

void pul1(int i) {
	int l = i << 1, r = l | 1;

	st1[i] = st1[l] + st1[r];
}

void build(int *aa, int n) {
	int i;

	h_ = 0;
	while (1 << h_ <= n)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i < n; i++) {
		st1[n_ + i] = aa[i];
		kk2[n_ + i] = 1;
	}
	for (i = n_ - 1; i > 0; i--)
		pul1(i);
}

void update1(int i, int a) {
	i += n_;
	st1[i] = a;
	while (i > 1)
		pul1(i >>= 1);
}

int queryl1(int r, long long s) {
	int l = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (s > st1[r])
				s -= st1[r--];
			else {
				while (r < n_)
					if (s <= st1[r << 1 | 1])
						r = r << 1 | 1;
					else
						s -= st1[r << 1 | 1], r = r << 1 | 0;
				return r - n_;
			}
		}
	return -1;
}

int queryr1(int l, long long s) {
	int r = n_ - 1;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1) {
			if (s > st1[l])
				s -= st1[l++];
			else {
				while (l < n_)
					if (s <= st1[l << 1 | 0])
						l = l << 1 | 0;
					else
						s -= st1[l << 1 | 0], l = l << 1 | 1;
				return l - n_;
			}
		}
	return n_;
}

void put2(int i, int x) {
	st2[i] += x;
	if (i < n_)
		lz2[i] += x;
}

void pus2(int i) {
	if (lz2[i])
		put2(i << 1 | 0, lz2[i]), put2(i << 1 | 1, lz2[i]), lz2[i] = 0;
}

void pul2(int i) {
	if (!lz2[i]) {
		int l = i << 1, r = l | 1;

		if (st2[l] < st2[r])
			st2[i] = st2[l], kk2[i] = kk2[l];
		else if (st2[l] > st2[r])
			st2[i] = st2[r], kk2[i] = kk2[r];
		else
			st2[i] = st2[l], kk2[i] = kk2[l] + kk2[r];
	}
}

void push2(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus2(i >> h);
}

void pull2(int i) {
	while (i > 1)
		pul2(i >>= 1);
}

void update2(int l, int r, int x) {
	int l_ = l += n_, r_ = r += n_;

	push2(l_), push2(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put2(l++, x);
		if ((r & 1) == 0)
			put2(r--, x);
	}
	pull2(l_), pull2(r_);
}

int query2(int l, int r) {
	int x = INF, k = 0;

	push2(l += n_), push2(r += n_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1) {
			if (x > st2[l])
				x = st2[l], k = 0;
			if (x == st2[l])
				k += kk2[l];
			l++;
		}
		if ((r & 1) == 0) {
			if (x > st2[r])
				x = st2[r], k = 0;
			if (x == st2[r])
				k += kk2[r];
			r--;
		}
	}
	return x == 0 ? k : 0;
}

void upd(int l, int r, int i, int x) {
	int j;

	j = max(queryl1(i - 1, aa[i]), l - 1);
	if (j < l || aa[j] > aa[i])
		update2(j + 1, i - 1, x);
	j = min(queryr1(i + 1, aa[i]), r + 1);
	if (j > r || aa[j] >= aa[i])
		update2(i + 1, j - 1, x);
}

int main() {
	int n, q, i, j;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	build(aa, n);
	scanf("%d", &q);
	for (i = 0; i < n; i++)
		upd(0, n - 1, i, 1);
	while (q--) {
		static char used[N];
		static int qu[N];
		int t, a, l, r, lg, cnt, h;

		scanf("%d", &t);
		if (t == 1) {
			scanf("%d%d", &i, &a), i--;
			cnt = 0;
			qu[cnt++] = i;
			for (lg = 0; lg <= LG; lg++) {
				j = queryl1(i - 1, 1 << lg);
				if (j >= 0 && !used[j])
					used[j] = 1, qu[cnt++] = j;
				j = queryr1(i + 1, 1 << lg);
				if (j < n && !used[j])
					used[j] = 1, qu[cnt++] = j;
			}
			for (h = 0; h < cnt; h++)
				upd(0, n - 1, qu[h], -1);
			aa[i] = a, update1(i, a);
			for (h = 0; h < cnt; h++)
				upd(0, n - 1, qu[h], 1);
			for (h = 0; h < cnt; h++)
				used[qu[h]] = 0;
		} else {
			scanf("%d%d", &l, &r), l--, r--;
			if (l == 0 && r == n - 1)
				printf("%d\n", query2(l, r));
			else {
				memset(st2, 0, n_ * 2 * sizeof *st2);
				memset(kk2, 0, n_ * 2 * sizeof *kk2);
				memset(lz2, 0, n_ * sizeof *lz2);
				for (i = 0; i < n_; i++)
					kk2[n_ + i] = 1;
				for (i = n_ - 1; i > 0; i--)
					pul2(i);
				for (i = l; i <= r; i++)
					upd(l, r, i, 1);
				printf("%d\n", query2(l, r));
				for (i = l; i <= r; i++)
					upd(l, r, i, -1);
			}
		}
	}
	return 0;
}

Compilation message

fish2.c: In function 'main':
fish2.c:167:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
fish2.c:169:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
fish2.c:171:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
fish2.c:179:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
fish2.c:181:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |    scanf("%d%d", &i, &a), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~
fish2.c:200:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |    scanf("%d%d", &l, &r), l--, r--;
      |    ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 65 ms 4456 KB Output is correct
3 Correct 68 ms 4404 KB Output is correct
4 Correct 64 ms 4372 KB Output is correct
5 Correct 67 ms 4412 KB Output is correct
6 Correct 51 ms 4344 KB Output is correct
7 Correct 46 ms 4492 KB Output is correct
8 Correct 50 ms 4368 KB Output is correct
9 Correct 46 ms 4428 KB Output is correct
10 Correct 55 ms 4392 KB Output is correct
11 Correct 53 ms 4468 KB Output is correct
12 Correct 47 ms 4384 KB Output is correct
13 Correct 48 ms 4428 KB Output is correct
14 Correct 58 ms 4384 KB Output is correct
15 Correct 55 ms 4360 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 65 ms 4456 KB Output is correct
3 Correct 68 ms 4404 KB Output is correct
4 Correct 64 ms 4372 KB Output is correct
5 Correct 67 ms 4412 KB Output is correct
6 Correct 51 ms 4344 KB Output is correct
7 Correct 46 ms 4492 KB Output is correct
8 Correct 50 ms 4368 KB Output is correct
9 Correct 46 ms 4428 KB Output is correct
10 Correct 55 ms 4392 KB Output is correct
11 Correct 53 ms 4468 KB Output is correct
12 Correct 47 ms 4384 KB Output is correct
13 Correct 48 ms 4428 KB Output is correct
14 Correct 58 ms 4384 KB Output is correct
15 Correct 55 ms 4360 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Execution timed out 4081 ms 4940 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 65 ms 4456 KB Output is correct
3 Correct 68 ms 4404 KB Output is correct
4 Correct 64 ms 4372 KB Output is correct
5 Correct 67 ms 4412 KB Output is correct
6 Correct 51 ms 4344 KB Output is correct
7 Correct 46 ms 4492 KB Output is correct
8 Correct 50 ms 4368 KB Output is correct
9 Correct 46 ms 4428 KB Output is correct
10 Correct 55 ms 4392 KB Output is correct
11 Correct 53 ms 4468 KB Output is correct
12 Correct 47 ms 4384 KB Output is correct
13 Correct 48 ms 4428 KB Output is correct
14 Correct 58 ms 4384 KB Output is correct
15 Correct 55 ms 4360 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 3432 ms 4772 KB Output is correct
18 Correct 1041 ms 6720 KB Output is correct
19 Correct 2501 ms 6092 KB Output is correct
20 Correct 840 ms 6592 KB Output is correct
21 Correct 3054 ms 6232 KB Output is correct
22 Correct 1063 ms 6704 KB Output is correct
23 Correct 3021 ms 5932 KB Output is correct
24 Correct 1000 ms 6836 KB Output is correct
25 Correct 2667 ms 6228 KB Output is correct
26 Correct 371 ms 7144 KB Output is correct
27 Correct 506 ms 7196 KB Output is correct
28 Correct 708 ms 6484 KB Output is correct
29 Correct 415 ms 7116 KB Output is correct
30 Correct 506 ms 7200 KB Output is correct
31 Correct 843 ms 6452 KB Output is correct
32 Correct 1002 ms 6768 KB Output is correct
33 Correct 1264 ms 6092 KB Output is correct
34 Correct 886 ms 7016 KB Output is correct
35 Correct 1025 ms 6656 KB Output is correct
36 Correct 859 ms 6476 KB Output is correct
37 Correct 946 ms 6256 KB Output is correct
38 Correct 636 ms 6256 KB Output is correct
39 Correct 511 ms 6828 KB Output is correct
40 Correct 247 ms 6768 KB Output is correct

Subtask #6
0 / 17.0

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