답안 #767355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
767355 2023-06-26T16:39:37 Z rainboy UFO (IZhO14_ufo) C
100 / 100
625 ms 31960 KB
#include <stdio.h>

#define NM	1000000

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

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

	for (i = 0; i < n_; i++)
		st[n_ + i] = i < n ? aa[i] : 0;
	for (i = n_ - 1; i > 0; i--)
		st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}

void update(int *st, int n_, int i, int x) {
	st[i += n_] = x;
	while (i > 1)
		i >>= 1, st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}

int next(int *st, int n_, int l, int a) {
	int r = n_ - 1;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1) {
			if (st[l] >= a) {
				while (l < n_)
					l = st[l << 1 | 0] >= a ? l << 1 | 0 : l << 1 | 1;
				return l - n_;
			}
			l++;
		}
	return n_;
}

int prev(int *st, int n_, int r, int a) {
	int l = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (st[r] >= a) {
				while (r < n_)
					r = st[r << 1 | 1] >= a ? r << 1 | 1 : r << 1 | 0;
				return r - n_;
			}
			r--;
		}
	return -1;
}

int main() {
	static int aa[NM], bb[NM], st1[NM * 4], st2[NM * 4];
	int n, n_, m, m_, q, t, l, i, j, sum, ans;

	scanf("%d%d%d%d%d", &n, &m, &t, &q, &l);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%d", &aa[i * m + j]);
	n_ = 1;
	while (n_ <= n)
		n_ <<= 1;
	m_ = 1;
	while (m_ <= m)
		m_ <<= 1;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++)
			bb[j] = aa[i * m + j];
		build(bb, st1 + i * m_ * 2, m, m_);
	}
	for (j = 0; j < m; j++) {
		for (i = 0; i < n; i++)
			bb[i] = aa[i * m + j];
		build(bb, st2 + j * n_ * 2, n, n_);
	}
	while (q--) {
		static char s[2];
		int k, a;

		scanf("%s", s);
		if (s[0] == 'W') {
			scanf("%d%d", &i, &a), i--;
			k = t, j = 0;
			while (k-- && (j = next(st1 + i * m_ * 2, m_, j, a)) < m) {
				aa[i * m + j]--;
				update(st1 + i * m_ * 2, m_, j, aa[i * m + j]);
				update(st2 + j * n_ * 2, n_, i, aa[i * m + j]);
				j++;
			}
		} else if (s[0] == 'E') {
			scanf("%d%d", &i, &a), i--;
			k = t, j = m - 1;
			while (k-- && (j = prev(st1 + i * m_ * 2, m_, j, a)) >= 0) {
				aa[i * m + j]--;
				update(st1 + i * m_ * 2, m_, j, aa[i * m + j]);
				update(st2 + j * n_ * 2, n_, i, aa[i * m + j]);
				j--;
			}
		} else if (s[0] == 'N') {
			scanf("%d%d", &j, &a), j--;
			k = t, i = 0;
			while (k-- && (i = next(st2 + j * n_ * 2, n_, i, a)) < n) {
				aa[i * m + j]--;
				update(st1 + i * m_ * 2, m_, j, aa[i * m + j]);
				update(st2 + j * n_ * 2, n_, i, aa[i * m + j]);
				i++;
			}
		} else {
			scanf("%d%d", &j, &a), j--;
			k = t, i = n - 1;
			while (k-- && (i = prev(st2 + j * n_ * 2, n_, i, a)) >= 0) {
				aa[i * m + j]--;
				update(st1 + i * m_ * 2, m_, j, aa[i * m + j]);
				update(st2 + j * n_ * 2, n_, i, aa[i * m + j]);
				i--;
			}
		}
	}
	for (i = 0; i < n; i++) {
		sum = 0;
		for (j = 0; j < m; j++) {
			sum += aa[i * m + j];
			if (j >= l - 1)
				bb[j - l + 1] = sum, sum -= aa[i * m + (j - l + 1)];
		}
		for (j = 0; j <= m - l; j++)
			aa[i * m + j] = bb[j];
	}
	for (j = 0; j <= m - l; j++) {
		sum = 0;
		for (i = 0; i < n; i++) {
			sum += aa[i * m + j];
			if (i >= l - 1)
				bb[i - l + 1] = sum, sum -= aa[(i - l + 1) * m + j];
		}
		for (i = 0; i <= n - l; i++)
			aa[i * m + j] = bb[i];
	}
	ans = 0;
	for (i = 0; i <= n - l; i++)
		for (j = 0; j <= m - l; j++)
			ans = max(ans, aa[i * m + j]);
	printf("%d\n", ans);
	return 0;
}

Compilation message

ufo.c: In function 'main':
ufo.c:56:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d%d%d%d%d", &n, &m, &t, &q, &l);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.c:59:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |    scanf("%d", &aa[i * m + j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.c:80:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
ufo.c:82:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |    scanf("%d%d", &i, &a), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~
ufo.c:91:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |    scanf("%d%d", &i, &a), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~
ufo.c:100:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |    scanf("%d%d", &j, &a), j--;
      |    ^~~~~~~~~~~~~~~~~~~~~
ufo.c:109:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |    scanf("%d%d", &j, &a), j--;
      |    ^~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 38 ms 1772 KB Output is correct
6 Correct 80 ms 13436 KB Output is correct
7 Correct 136 ms 27340 KB Output is correct
8 Correct 119 ms 27332 KB Output is correct
9 Correct 191 ms 27192 KB Output is correct
10 Correct 224 ms 27332 KB Output is correct
11 Correct 164 ms 27724 KB Output is correct
12 Correct 223 ms 27356 KB Output is correct
13 Correct 274 ms 27368 KB Output is correct
14 Correct 249 ms 27708 KB Output is correct
15 Correct 289 ms 27256 KB Output is correct
16 Correct 135 ms 27712 KB Output is correct
17 Correct 404 ms 27300 KB Output is correct
18 Correct 127 ms 18860 KB Output is correct
19 Correct 166 ms 27688 KB Output is correct
20 Correct 625 ms 31960 KB Output is correct