제출 #213455

#제출 시각아이디문제언어결과실행 시간메모리
213455BlagojceRectangles (IOI19_rect)C++14
37 / 100
5114 ms342780 KiB
#include <bits/stdc++.h> #define fr(i, n, m) for(int i = (n); i < (m); i ++) #define st first #define nd second #define pb push_back #define pq priority_queue #define all(x) begin(x), end(x) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; ll const inf = 1e9; ll const mod = 1e9 + 7; ld const eps = 1e-13; #include "rect.h" int n, m; int a[2500][2500]; vector<int> le[2500][2500]; vector<int> up[2500][2500]; void find_lefts(){ fr(i, 0, n){ fr(j, 0, m){ int MAX = 0; for(int k = j - 1; k >= 0; k --){ if(j - k > 1 && MAX < a[i][j] && MAX < a[i][k]){ le[i][j].pb(k); } MAX = max(MAX, a[i][k]); } } } } void find_ups(){ fr(i, 0, n){ fr(j, 0, m){ int MAX = 0; for(int k = i - 1; k >= 0; k --){ if(i - k > 1 && MAX < a[i][j] && MAX < a[k][j]){ up[i][j].pb(k); } MAX = max(MAX, a[k][j]); } } } } long long count_rectangles(std::vector<std::vector<int> > v) { /* cin >> n >> m; v.resize(n); fr(i, 0, n){ v[i].resize(m); fr(j, 0, m){ cin >> v[i][j]; } } */ n = v.size(); m = v[0].size(); fr(i, 0, n){ fr(j, 0, m){ a[i][j] = v[i][j]; } } find_lefts(); find_ups(); bool cnt[n][m]; bool cnt2[n][m]; int ANS = 0; fr(i, 2, n){ fr(j, 2, m){ memset(cnt, false, sizeof(cnt)); memset(cnt2, false, sizeof(cnt2)); for(int k = i - 1; k > 0; k --){ for(auto u : le[k][j]){ if(k == i - 1 || cnt[k][u]){ cnt[k - 1][u] = true; } } } for(int k = j - 1; k > 0; k --){ for(auto u : up[i][k]){ if(k == j - 1 || cnt2[u][k]){ cnt2[u][k - 1] = true; if(cnt[u][k - 1]) ANS ++; } } } } } // cout << ANS<<endl; return ANS; } /* int main() { freopen("in.txt", "r", stdin); vector<vector<int> > v; count_rectangles(v); return 0; }*/ /* 6 5 4 8 7 5 6 7 4 10 3 5 9 7 20 14 2 9 14 7 3 6 5 7 5 2 7 4 5 13 5 6 */
#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...