| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 527515 |
2022-02-17T14:32:29 Z |
eecs |
Sandcastle 2 (JOI22_ho_t5) |
C++17 |
|
6 ms |
1100 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 52000;
const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
int h, w, ans, a[maxn], sa[maxn], sb[maxn], cnt[maxn];
int num[9][9][maxn], tmp[9][6][maxn], res[6][6][maxn], pre[6][maxn];
int id(int x, int y) {
return (x - 1) * w + y;
}
int main() {
scanf("%d %d", &h, &w);
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
scanf("%d", &a[id(i, j)]);
}
}
for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) {
for (int lx : {i - 2, i - 1, i}) for (int rx : {i, i + 1, i + 2}) {
for (int ly : {j - 2, j - 1, j}) for (int ry : {j, j + 1, j + 2}) {
int d = 0;
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x < lx || x > rx || y < ly || y > ry) continue;
int mx = -1, foo = 0, bar;
for (int _k = 0; _k < 4; _k++) {
int p = x + dx[_k], q = y + dy[_k];
if (p < lx || p > rx || q < ly || q > ry) continue;
if (a[id(p, q)] < a[id(x, y)] && a[id(p, q)] > mx) mx = a[id(p, q)], foo = p, bar = q;
}
if (foo == i && bar == j) { d = 1; break; }
}
if (!d) num[(i - lx) * 3 + rx - i][(j - ly) * 3 + ry - j][id(i, j)]++;
}
}
}
for (int i = 0; i < 9; i++) {
for (int j = 1; j <= h * w; j++) {
tmp[i][0][j] = num[i][0][j];
tmp[i][1][j] = num[i][1][j] + num[i][3][j + 1];
tmp[i][2][j] = num[i][2][j] + num[i][4][j + 1] + num[i][6][j + 2];
tmp[i][3][j] = num[i][2][j] + num[i][5][j + 1];
tmp[i][4][j] = num[i][7][j] + num[i][6][j + 1];
tmp[i][5][j] = num[i][8][j];
}
}
for (int i = 0; i < 6; i++) {
for (int j = 1; j <= h * w; j++) {
res[0][i][j] = tmp[0][i][j];
res[1][i][j] = tmp[1][i][j] + tmp[3][i][j + w];
res[2][i][j] = tmp[2][i][j] + tmp[4][i][j + w] + tmp[6][i][j + 2 * w];
res[3][i][j] = tmp[2][i][j] + tmp[5][i][j + w];
res[4][i][j] = tmp[7][i][j] + tmp[6][i][j + w];
res[5][i][j] = tmp[8][i][j];
pre[i][j] = pre[i][j - 1] + res[i][5][j];
}
}
auto calc = [&](int k, int x, int ly, int ry) {
if (ry <= ly + 2) return res[k][ry - ly][id(x, ly)];
if (ry == ly + 3) return res[k][3][id(x, ly)] + res[k][4][id(x, ly + 2)];
int t = res[k][3][id(x, ly)] + res[k][4][id(x, ry - 1)];
return t + pre[k][id(x, ry - 2)] - pre[k][id(x, ly + 1)];
};
for (int ly = 1; ly <= w; ly++) {
for (int ry = ly; ry <= w; ry++) {
fill(sa, sa + h + 1, 0), fill(sb, sb + h + 1, 0);
int v8 = 0;
for (int i = 1; i < h; i++) {
if (i > 3) sa[i - 2] += v8, sb[i + 1] += v8;
sa[i] -= calc(3, i, ly, ry);
sb[i + 1] += calc(4, i, ly, ry);
v8 += calc(5, i, ly, ry);
}
for (int i = 1; i <= h; i++) {
if (i > 3) {
cnt[sa[i - 3] + 2 * w]++;
ans += cnt[sb[i] + 2 * w - 1];
}
for (int j = 0; j <= min(i - 1, 2); j++) {
if (calc(j, i - j, ly, ry) == 1) ans++;
}
}
for (int i = 4; i <= h; i++) {
cnt[sa[i - 3] + 2 * w]--;
}
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | scanf("%d %d", &h, &w);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:17:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | scanf("%d", &a[id(i, j)]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:33:41: warning: 'bar' may be used uninitialized in this function [-Wmaybe-uninitialized]
33 | if (foo == i && bar == j) { d = 1; break; }
| ~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Runtime error |
6 ms |
960 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
