제출 #1196397

#제출 시각아이디문제언어결과실행 시간메모리
1196397stdfloatRectangles (IOI19_rect)C++20
72 / 100
5099 ms686244 KiB
#include <bits/stdc++.h> #include "rect.h" // #include "grader.cpp" using namespace std; using ll = long long; ll count_rectangles(vector<vector<int>> a) { int n = (int)a.size(), m = (int)a[0].size(); vector<vector<int>> L(n, vector<int>(m)), R = L, U = L, D = L; for (int i = 0; i < n; i++) { stack<int> s; for (int j = 0; j < m; j++) { while (!s.empty() && a[i][s.top()] < a[i][j]) s.pop(); L[i][j] = (s.empty() ? 0 : s.top()); s.push(j); } while (!s.empty()) s.pop(); for (int j = m - 1; j >= 0; j--) { while (!s.empty() && a[i][j] > a[i][s.top()]) s.pop(); R[i][j] = (s.empty() ? m - 1 : s.top()); s.push(j); } } for (int i = 0; i < m; i++) { stack<int> s; for (int j = 0; j < n; j++) { while (!s.empty() && a[s.top()][i] < a[j][i]) s.pop(); U[j][i] = (s.empty() ? 0 : s.top()); s.push(j); } while(!s.empty()) s.pop(); for (int j = n - 1; j >= 0; j--) { while (!s.empty() && a[j][i] > a[s.top()][i]) s.pop(); D[j][i] = (s.empty() ? n - 1 : s.top()); s.push(j); } } vector<vector<vector<int>>> sp(m, vector<vector<int>>(n, vector<int>(13))); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) sp[i][j][0] = L[j][i]; for (int j = 1; j < 13; j++) { for (int k = 0; k + (1 << j) <= n; k++) sp[i][k][j] = max(sp[i][k][j - 1], sp[i][k + (1 << (j - 1))][j - 1]); } } vector<int> lg(n + 1); for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1; ll cnt = 0; for (int i = 1; i < n - 1; i++) { for (int j = 1; j < m - 1; j++) { int mn = INT_MAX; for (int k = i; k < D[i - 1][j] && j < R[k][j - 1]; k++) { mn = min(mn, R[k][j - 1]); for (int l = j; l < mn && k < D[i - 1][l] && U[k + 1][l] < i; l++) { int y = lg[k - i + 1]; cnt += max(sp[l + 1][i][y], sp[l + 1][k - (1 << y) + 1][y]) < j; // bool tr = true; // for (int m = i; m <= k && tr; m++) // tr = (L[m][l + 1] < j); // cnt += tr; } } } } return cnt; }
#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...