Submission #1202440

#TimeUsernameProblemLanguageResultExecution timeMemory
1202440LucaIlieRectangles (IOI19_rect)C++20
25 / 100
5096 ms131532 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 2500; const int INF = 1e9; int n, m; long long ans = 0; int mat[MAX_N + 2][MAX_N + 2]; int leftG[MAX_N + 2][MAX_N + 2], leftGE[MAX_N + 2][MAX_N + 2]; int rightG[MAX_N + 2][MAX_N + 2], rightGE[MAX_N + 2][MAX_N + 2]; int upG[MAX_N + 2][MAX_N + 2], upGE[MAX_N + 2][MAX_N + 2]; int downG[MAX_N + 2][MAX_N + 2], downGE[MAX_N + 2][MAX_N + 2]; vector<int> st; void init(); void solve(bool eqL, bool eqC) { // printf("%d %d\n", eqL, eqC); init(); /* for (int l = 1; l <= n; l++) { for (int c = 1; c <= m; c++) printf("%d ", leftGE[l][c]); printf("\n"); } printf("\n"); for (int l = 1; l <= n; l++) { for (int c = 1; c <= m; c++) printf("%d ", rightGE[l][c]); printf("\n"); } printf("\n"); for (int l = 1; l <= n; l++) { for (int c = 1; c <= m; c++) printf("%d ", mat[l][c]); printf("\n"); } printf("\n"); */ for (int l1 = 1; l1 <= n; l1++) { for (int c1 = 1; c1 <= m; c1++) { int c2 = rightGE[l1 + 1][c1], l2 = downGE[l1][c1 + 1]; /* if (l2 > n || c2 > m || l2 - l1 <= 1 || c2 - c1 <= 1) continue; if (mat[l1 + 1][c1] == mat[l1 + 1][c2] && eqC) continue; if (mat[l1][c1 + 1] == mat[l2][c1 + 1] && eqL) continue; */ for (int l2 = l1; l2 <= n; l2++) { for (int c2 = c1; c2 <= m; c2++) { if (l2 > n || c2 > m || l2 - l1 <= 1 || c2 - c1 <= 1) continue; bool ok = true; for (int l = l1 + 1; l <= l2 - 1; l++) ok &= (rightGE[l][c1] == c2 || (leftGE[l][c2] == c1)); for (int c = c1 + 1; c <= c2 - 1; c++) ok &= (downGE[l1][c] == l2 || (upGE[l2][c] == l1)); int afl1 = l1, afl2 = l2, afc1 = c1, afc2 = c2; if (eqL) afl1 = n + 1 - l2, afl2 = n + 1 - l1; if (eqC) afc1 = m + 1 - c2, afc2 = m + 1 - c1; /* if (ok) printf("%d %d %d %d\n", afl1, afc1, afl2, afc2); if (ok) printf("%d %d %d %d\n\n", l1, c1, l2, c2); */ ans += ok; } } } } //printf("\n\n"); } void rotVert() { for (int l = 1; l <= n; l++) { for (int c = 1; c <= m / 2; c++) { swap(mat[l][c], mat[l][m + 1 - c]); swap(upG[l][c], upG[l][m + 1 - c]); swap(upGE[l][c], upGE[l][m + 1 - c]); swap(downGE[l][c], downGE[l][m + 1 - c]); swap(downG[l][c], downG[l][m + 1 - c]); swap(leftG[l][c], rightG[l][m + 1 - c]); swap(leftGE[l][c], rightGE[l][m + 1 - c]); swap(rightG[l][c], leftG[l][m + 1 - c]); swap(rightGE[l][c], leftGE[l][m + 1 - c]); leftG[l][c] = m + 1 - leftG[l][c]; leftGE[l][c] = m + 1 - leftGE[l][c]; rightG[l][c] = m + 1 - rightG[l][c]; rightGE[l][c] = m + 1 - rightGE[l][c]; } } } void rotHoriz() { for (int l = 1; l <= n / 2; l++) { for (int c = 1; c <= m; c++) { swap(mat[l][c], mat[n + 1 - l][c]); swap(leftG[l][c], leftG[n + 1 - l][c]); swap(leftGE[l][c], leftGE[n + 1 - l][c]); swap(rightG[l][c], rightG[n + 1 - l][c]); swap(rightGE[l][c], rightGE[n + 1 - l][c]); swap(upG[l][c], downG[n + 1 - l][c]); swap(upGE[l][c], downGE[n + 1 - l][c]); swap(downG[l][c], upG[n + 1 - l][c]); swap(downGE[l][c], upGE[n + 1 - l][c]); upG[l][c] = n + 1 - upG[l][c]; upGE[l][c] = n + 1 - upGE[l][c]; downG[l][c] = n + 1 - downG[l][c]; downGE[l][c] = n + 1 - downGE[l][c]; } } } void init() { for (int l = 1; l <= n; l++) { mat[l][0] = INF; st.clear(); st.push_back(0); for (int c = 1; c <= m; c++) { while (mat[l][c] > mat[l][st.back()]) st.pop_back(); leftGE[l][c] = st.back(); st.push_back(c); } st.clear(); st.push_back(0); for (int c = 1; c <= m; c++) { while (mat[l][c] >= mat[l][st.back()]) st.pop_back(); leftG[l][c] = st.back(); st.push_back(c); } mat[l][m + 1] = INF; st.clear(); st.push_back(m + 1); for (int c = m; c >= 1; c--) { while (mat[l][c] > mat[l][st.back()]) st.pop_back(); rightGE[l][c] = st.back(); st.push_back(c); } st.clear(); st.push_back(m + 1); for (int c = m; c >= 1; c--) { while (mat[l][c] >= mat[l][st.back()]) st.pop_back(); rightG[l][c] = st.back(); st.push_back(c); } } for (int c = 1; c <= m; c++) { mat[0][c] = INF; st.clear(); st.push_back(0); for (int l = 1; l <= n; l++) { while (mat[l][c] > mat[st.back()][c]) st.pop_back(); upGE[l][c] = st.back(); st.push_back(l); } st.clear(); st.push_back(0); for (int l = 1; l <= n; l++) { while (mat[l][c] >= mat[st.back()][c]) st.pop_back(); upG[l][c] = st.back(); st.push_back(l); } mat[n + 1][c] = INF; st.clear(); st.push_back(n + 1); for (int l = n; l >= 1; l--) { while (mat[l][c] > mat[st.back()][c]) st.pop_back(); downGE[l][c] = st.back(); st.push_back(l); } st.clear(); st.push_back(n + 1); for (int l = n; l >= 1; l--) { while (mat[l][c] >= mat[st.back()][c]) st.pop_back(); downG[l][c] = st.back(); st.push_back(l); } } } long long count_rectangles(vector<vector<int>> a) { n = a.size(), m = a[0].size(); for (int l = 1; l <= n; l++) { for (int c = 1; c <= m; c++) mat[l][c] = a[l - 1][c - 1]; } init(); /* for (int l = 1; l <= n; l++) { for (int c = 1; c <= m; c++) printf("%d ", leftG[l][c]); printf("\n"); } */ /* for (int l = 1; l <= n; l++) { for (int c = 1; c <= m; c++) printf("%d ", downGE[l][c]); printf("\n"); } */ for (int a = 0; a < 1; a++) { for (int b = 0; b < 1; b++) { solve(a, b); //rotVert(); } //rotHoriz(); } 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...