| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 767355 |
2023-06-26T16:39:37 Z |
rainboy |
UFO (IZhO14_ufo) |
C |
|
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--;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
