#include <bits/stdc++.h> #include "dzialka.h" #include "message.h" using namespace std; using ll = long long; const int MAXN = 2e3+5; struct rect { int h, w; }; int c[MAXN][MAXN], d[MAXN][MAXN], sz; rect S[MAXN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int id = MyNodeId(); if (id) return 0; int n = GetFieldHeight(), m = GetFieldWidth(); for (int i = 1; i <= n; i++) { sz = 0; for (int j = 1; j <= m+1; j++) { if (j <= m) { bool ok = IsUsableCell(i-1, j-1); if (ok) d[i][j] = d[i-1][j] + 1; } int w = 0; while (sz && S[sz].h >= d[i][j]) { int h = max(S[sz-1].h, d[i][j]); w += S[sz].w; c[h+1][w]++; c[S[sz].h+1][w]--; sz--; } sz++; S[sz] = {d[i][j], w+1}; } } ll res = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { c[i+1][j] += c[i][j]; } int c1 = 0, c2 = 0; for (int j = m; j > 0; j--) { c1 += c[i][j]; c2 += c1; c[i][j] = c2; res += c[i][j]; } } cout << res << "\n"; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #include <bits/stdc++.h> #include "dzialka.h" #include "message.h" using namespace std; using ll = long long; const int MAXN = 2e3+5; struct rect { int h, w; }; int c[MAXN][MAXN], d[MAXN][MAXN], sz; rect S[MAXN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int id = MyNodeId(); if (id) return 0; int n = GetFieldHeight(), m = GetFieldWidth(); for (int i = 1; i <= n; i++) { sz = 0; for (int j = 1; j <= m+1; j++) { if (j <= m) { bool ok = IsUsableCell(i-1, j-1); if (ok) d[i][j] = d[i-1][j] + 1; } int w = 0; while (sz && S[sz].h >= d[i][j]) { int h = max(S[sz-1].h, d[i][j]); w += S[sz].w; c[h+1][w]++; c[S[sz].h+1][w]--; sz--; } sz++; S[sz] = {d[i][j], w+1}; } } ll res = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { c[i+1][j] += c[i][j]; } int c1 = 0, c2 = 0; for (int j = m; j > 0; j--) { c1 += c[i][j]; c2 += c1; c[i][j] = c2; res += c[i][j]; } } cout << res << "\n"; } |