Submission #594561

#TimeUsernameProblemLanguageResultExecution timeMemory
594561piOOESandcastle 2 (JOI22_ho_t5)C++17
100 / 100
2652 ms4200 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; //O((H * W)^2) //I also came up with O((H * W)^2) solution, but didn't know how to optimize it to O(min(H, W) * H * W) //so now this is Radewoosh's solution int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; bool swapped = false; if (n > m) { swapped = true; swap(n, m); } vector<vector<int>> a(n, vector<int>(m)); vector<int> yy; for (int i = 0; i < (swapped ? m : n); ++i) { for (int j = 0; j < (swapped ? n : m); ++j) { if (!swapped) { cin >> a[i][j]; yy.push_back(a[i][j]); } else { cin >> a[j][i]; yy.push_back(a[j][i]); } } } sort(yy.begin(), yy.end()); yy.resize(unique(yy.begin(), yy.end()) - yy.begin()); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { a[i][j] = lower_bound(yy.begin(), yy.end(), a[i][j]) - yy.begin() + 1; } } const int dx[4] = {-1, 0, 1, 0}; const int dy[4] = {0, 1, 0, -1}; // 0 // 3 1 // 2 auto solveM = [&](int k) { ll ans = 0; for (int i = 0; i < m;) { int j = i + 1; while (j < m && a[k][j] < a[k][j - 1]) { j += 1; } int len = j - i; ans += len * ((ll)len - 1) / 2; i = j; } for (int i = m - 1; i > -1;) { int j = i - 1; while (j > -1 && a[k][j] < a[k][j + 1]) { j -= 1; } int len = i - j; ans += len * ((ll)len - 1) / 2; i = j; } return ans; }; auto solveN = [&](int k) { ll ans = 0; for (int i = 0; i < n;) { int j = i + 1; while (j < n && a[j][k] < a[j - 1][k]) { j += 1; } int len = j - i; ans += len * ((ll)len - 1) / 2; i = j; } for (int i = n - 1; i > -1;) { int j = i - 1; while (j > -1 && a[j][k] < a[j + 1][k]) { j -= 1; } int len = i - j; ans += len * ((ll)len - 1) / 2; i = j; } return ans; }; ll ans = 0; if (n == 1) { ans += solveM(0) + m; } else { int diff[16][n][m]; memset(diff, 0, sizeof(diff)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { for (int mask = 0; mask < 16; ++mask) { int lower = 0; bool big = false; for (int k = 0; k < 4; ++k) { if (mask >> k & 1) { int nx = i + dx[k]; int ny = j + dy[k]; if (nx >= 0 && nx < n && ny >= 0 && ny < m) { if (a[nx][ny] < a[i][j]) { lower = max(lower, a[nx][ny]); } else { big = true; } } } } diff[mask][i][j] = a[i][j] - lower + (big ? 0 : n * m + 1 - a[i][j]); } } } //now handle rectangles with width or length = 1 for (int i = 0; i < n; ++i) { ans += solveM(i); } for (int i = 0; i < m; ++i) { ans += solveN(i); } ans += n * m; //main part! for (int x1 = 0; x1 < n; ++x1) { for (int x2 = x1 + 1; x2 < n; ++x2) { vector<int> valMid(m), valR(m), valL(m); for (int y = 0; y < m; ++y) { for (int x = x1; x <= x2; ++x) { valMid[y] += diff[15 - (x == x1 ? 1 : 0) - (x == x2 ? 4 : 0)][x][y]; valL[y] += diff[15 - 8 - (x == x1 ? 1 : 0) - (x == x2 ? 4 : 0)][x][y]; valR[y] += diff[15 - 2 - (x == x1 ? 1 : 0) - (x == x2 ? 4 : 0)][x][y]; } } map<int, int> cnt; int prefix = 0; for (int y1 = 0; y1 < m; ++y1) { if (y1 > 0) { prefix += valMid[y1 - 1]; ++cnt[prefix - valL[y1 - 1]]; } ans += cnt[prefix + valR[y1] - (n * m + 1)]; } } } } cout << ans; 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...