제출 #1078059

#제출 시각아이디문제언어결과실행 시간메모리
1078059BoasRectangles (IOI19_rect)C++17
0 / 100
903 ms1048576 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; // #define int long long #define sz(x) (int)x.size() #define pb push_back #define loop(x, i) for (int i = 0; i < x; i++) #define rev(x, i) for (int i = (int)x - 1; i >= 0; i--) #define ALL(x) begin(x), end(x) typedef signed i32; typedef pair<int, int> ii; typedef vector<i32> vi32; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<bool> vb; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<vi32> vvi32; typedef vector<vii> vvii; typedef vector<vb> vvb; typedef vector<vvb> vvvb; long long count_rectangles(vvi a) { int n = sz(a); // h int m = sz(a[0]); // w vvvb validUp(n, vvb(m, vb(m))); vvvb validDown(n, vvb(m, vb(m))); vvvb validL(m, vvb(n, vb(n))); vvvb validR(m, vvb(n, vb(n))); // omwisselen voor cache friendlyness? vvvi pSumValR(n, vvi(n, vi(m))); for (int c = 1; c < m - 1; c++) { for (int r1 = 1; r1 < n - 1; r1++) { bool valL = 1; bool valR = 1; for (int r2 = r1; r2 < n - 1; r2++) { valL &= (a[r2][c] < a[r2][c - 1]); valR &= (a[r2][c] < a[r2][c + 1]); validL[c][r1][r2] = valL; validR[c][r1][r2] = valR; } } } for (int r = 1; r < n - 1; r++) { for (int c1 = 1; c1 < m - 1; c1++) { bool valUp = 1; bool valDown = 1; for (int c2 = c1; c2 < m - 1; c2++) { valUp &= (a[r][c2] < a[r - 1][c2]); valDown &= (a[r][c2] < a[r + 1][c2]); validUp[r][c1][c2] = valUp; validDown[r][c1][c2] = valDown; } } } for (int r1 = 1; r1 < n - 1; r1++) { for (int r2 = r1; r2 < n - 1; r2++) { for (int c = 1; c < m - 1; c++) { pSumValR[r1][r2][c] = pSumValR[r1][r2][c - 1] + (validR[c][r1][r2]); } } } long long res = 0; for (int c = 1; c < m - 1; c++) { for (int r1 = 1; r1 < n - 1; r1++) { for (int r2 = r1; r2 < n - 1; r2++) { if (!validL[c][r1][r2]) break; int lo = c, hi = m - 2; int ans = -1; while (hi >= lo) { int c2 = (lo + hi) / 2; if (validUp[r1][c][c2] && validDown[r2][c][c2]) { ans = c2; lo = c2 + 1; } else { hi = c2 - 1; } } if (ans == -1) continue; res += pSumValR[r1][r2][ans] - pSumValR[r1][r2][c - 1]; } } } return res; }
#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...