Submission #767354

#	Time	Username	Problem	Language	Result	Execution time	Memory
767354		rainboy	UFO (IZhO14_ufo)	C11	70 / 100	624 ms	32080 KiB

ufo

#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_, 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 (stderr)

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--;
      |    ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 100