Submission #632390

#TimeUsernameProblemLanguageResultExecution timeMemory
632390Ooops_sorrySandcastle 2 (JOI22_ho_t5)C++14
9 / 100
40 ms14804 KiB
#include<bits/stdc++.h> using namespace std; mt19937 rnd(51); #define ll long long #define pb push_back #define ld long double int n, m, INF; vector<vector<int>> a, any; vector<pair<int,int>> d{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; vector<bool> used(4); vector<vector<vector<int>>> side, two; bool check(int i, int j) { return i >= 0 && i < n && j >= 0 && j < m; } int get_max(int i, int j, vector<int> ban = {}) { int mx = -1; for (auto to : ban) { used[to] = 1; } for (int k = 0; k < 4; k++) { if (used[k]) { continue; } int x = i + d[k].first, y = j + d[k].second; if (check(x, y) && a[x][y] < a[i][j]) { mx = max(mx, a[x][y]); } } for (auto to : ban) { used[to] = 0; } return (mx == -1 ? 0 : a[i][j] - mx); } void build() { int h = max(n, m), w = min(n, m); a.resize(h); any.resize(h); side.resize(h); two.resize(h); for (int i = 0; i < h; i++) { a[i].resize(w); any[i].resize(w); side[i].resize(w); two[i].resize(w); } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { side[i][j].resize(4); two[i][j].resize(4); } } } // 0 -> U // 1 -> R // 2 -> D // 3 -> L signed main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif // LOCAL ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; INF = n * m; build(); if (n < m) { swap(n, m); for (int j = 0; j < m; j++) { for (int i = 0; i < n; i++) { cin >> a[i][j]; } } } else { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; } } } ll ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { any[i][j] = get_max(i, j); for (int k = 0; k < 4; k++) { side[i][j][k] = get_max(i, j, {k}); two[i][j][k] = get_max(i, j, {k, (k + 1) % 4}); } } } for (int i = 0; i < n; i++) { int last = 2, cnt = 0; for (int j = 1; j < m; j++) { if ((last ^ (a[i][j - 1] < a[i][j])) == 1) { ans += 1ll * cnt * (cnt + 1) / 2; cnt = 1; } else { cnt++; } last = (a[i][j - 1] < a[i][j]); } ans += 1ll * cnt * (cnt + 1) / 2; } for (int j = 0; j < m; j++) { int last = 2, cnt = 0; for (int i = 1; i < n; i++) { if ((last ^ (a[i - 1][j] < a[i][j])) == 1) { ans += 1ll * cnt * (cnt + 1) / 2; cnt = 1; } else { cnt++; } last = (a[i - 1][j] < a[i][j]); } ans += 1ll * cnt * (cnt + 1) / 2; } ans += n * m; cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...