Submission #1215218

#TimeUsernameProblemLanguageResultExecution timeMemory
1215218lrnnzRectangles (IOI19_rect)C++20
37 / 100
5096 ms22852 KiB
#include <bits/stdc++.h> #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <iomanip> #include "rect.h" using namespace std; #define all(a) (a).begin(), (a).end() #define sz(a) (int)(a).size() #define ll long long #define ld long double #define ui uint64_t #define cont(set, element) ((set).find(element) != (set).end()) /********* DEBUG *********/ template <typename T> void outvec(const vector<T>& Z){ for (const T& x : Z) cout << x << ' '; cout << "\n"; } void printVariable(const any& var) { if (!var.has_value()) { cout << "null"; return; } if (var.type() == typeid(int)) { cout << any_cast<int>(var); } else if (var.type() == typeid(double)) { cout << any_cast<double>(var); } else if (var.type() == typeid(float)) { cout << any_cast<float>(var); } else if (var.type() == typeid(char)) { cout << any_cast<char>(var); } else if (var.type() == typeid(bool)) { cout << (any_cast<bool>(var) ? "true" : "false"); } else if (var.type() == typeid(string)) { cout << any_cast<string>(var); } else if (var.type() == typeid(const char*)) { cout << any_cast<const char*>(var); } else if (var.type() == typeid(long long)) { cout << any_cast<long long>(var); } else { cout << "[unknown type]"; } } template<typename... Args> void outval(Args... args) { vector<any> variables = {args...}; for (size_t i = 0; i < variables.size(); ++i) { printVariable(variables[i]); if (i != variables.size() - 1) { cout << " "; } } cout << "\n"; } #define sp << " " << /********* DEBUG *********/ const ll MOD = 1e9+7; const ll MOD2 = 998244353; const ll inf = 1e18; const ll mxN = 2000005; ll count_rectangles(vector<vector<int>> a) { int n = a.size(), m = a[0].size(); ll ans = 0; // n = 0, m = 1 vector<int> maxRow(n), maxCol(m); vector<bool> validCol(m); for (int i = 1; i < n-1; i++){ for (int j = 1; j < m-1; j++){ for (int r = i; r < n-1; r++){ bool ok = true; for (int c = j; c < m-1; c++){ if (c == j) maxRow[r] = a[r][c]; if (r == i) maxCol[c] = a[r][c], validCol[c] = true; maxRow[r] = max(maxRow[r], a[r][c]); maxCol[c] = max(maxCol[c], a[r][c]); bool IsValidRow = maxRow[r] < a[r][j-1] && maxRow[r] < a[r][c+1]; bool IsValidCol = maxCol[c] < a[i-1][c] && maxCol[c] < a[r+1][c]; validCol[c] = IsValidRow && validCol[c]; if (!IsValidCol) ok = false; if (!validCol[c] || !ok) continue; ans++; } } } } return ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...