답안 #767343

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
767343 2023-06-26T16:19:29 Z rainboy UFO (IZhO14_ufo) C
50 / 100
618 ms 28744 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_, 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_, 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_, m_, j, a)) < m) {
				aa[i * m + j]--;
				update(st1 + i * m_, m_, j, aa[i * m + j]);
				update(st2 + j * n_, 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_, m_, j, a)) >= 0) {
				aa[i * m + j]--;
				update(st1 + i * m_, m_, j, aa[i * m + j]);
				update(st2 + j * n_, 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(st1 + j * n_, n_, i, a)) < n) {
				aa[i * m + j]--;
				update(st1 + i * m_, m_, j, aa[i * m + j]);
				update(st2 + j * n_, n_, i, aa[i * m + j]);
				i++;
			}
		} else {
			scanf("%d%d", &j, &a), j--;
			k = t, i = n - 1;
			while (k-- && (i = prev(st1 + j * n_, n_, i, a)) >= 0) {
				aa[i * m + j]--;
				update(st1 + i * m_, m_, j, aa[i * m + j]);
				update(st2 + j * n_, 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 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 6 ms 568 KB Output isn't correct
5 Incorrect 31 ms 1876 KB Output isn't correct
6 Incorrect 78 ms 11028 KB Output isn't correct
7 Correct 131 ms 24524 KB Output is correct
8 Correct 110 ms 20836 KB Output is correct
9 Incorrect 144 ms 19468 KB Output isn't correct
10 Correct 140 ms 19948 KB Output is correct
11 Incorrect 134 ms 19904 KB Output isn't correct
12 Correct 150 ms 19944 KB Output is correct
13 Correct 231 ms 20836 KB Output is correct
14 Correct 274 ms 19772 KB Output is correct
15 Incorrect 165 ms 21536 KB Output isn't correct
16 Correct 129 ms 22024 KB Output is correct
17 Incorrect 214 ms 25336 KB Output isn't correct
18 Correct 111 ms 17300 KB Output is correct
19 Incorrect 153 ms 22484 KB Output isn't correct
20 Correct 618 ms 28744 KB Output is correct