Submission #1243273

#TimeUsernameProblemLanguageResultExecution timeMemory
1243273nvujicaRectangles (IOI19_rect)C++20
0 / 100
0 ms580 KiB
#include "rect.h" #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 2510; int a[maxn][maxn]; int desno[maxn][maxn]; int dolje[maxn][maxn]; int pref[maxn][maxn]; int suma(int x1, int y1, int x2, int y2){ return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1]; } long long count_rectangles(vector<vector<int> > b) { int n = b.size(); int m = b[0].size(); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ a[i + 1][j + 1] = b[i][j]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ pref[i][j] = pref[i][j - 1] + pref[i - 1][j] - pref[i - 1][j - 1] + a[i][j]; } } // cout << suma(1, 1, 3, 3) << ' ' << suma(2, 2, 2, 2) << endl; for(int i = 1; i <= n; i++){ desno[i][m + 1] = m + 1; for(int j = m; j >= 1; j--){ desno[i][j] = desno[i][j + 1]; if(a[i][j]) desno[i][j] = j; } } for(int j = 1; j <= m; j++){ dolje[n + 1][j] = n + 1; for(int i = n; i >= 1; i--){ dolje[i][j] = dolje[i + 1][j]; if(a[i][j]) dolje[i][j] = i; } } int ans = 0; for(int i = 1; i < n; i++){ for(int j = 1; j < m; j++){ if(!a[i][j] || a[i + 1][j + 1]) continue; int r = desno[i + 1][j + 1]; int d = dolje[i + 1][j + 1]; if(d == i + 1 || r == j + 1) continue; if(suma(i, j, d, r) == 2 * (d - i) + 2 * (r - j) && suma(i + 1, j + 1, d - 1, r - 1) == 0) 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...