제출 #692495

#제출 시각아이디문제언어결과실행 시간메모리
692495sharaelongRectangles (IOI19_rect)C++17
23 / 100
1785 ms534036 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; struct DisjointSet { int n; vector<int> parent, rank; DisjointSet(int _n) : n(_n) { parent.resize(n); iota(parent.begin(), parent.end(), 0); rank.resize(n, 0); } int find(int u) { return parent[u] = (u == parent[u] ? u : find(parent[u])); } void merge(int u, int v) { u = find(u); v = find(v); if (u == v) return; if (rank[u] > rank[v]) swap(u, v); parent[u] = v; if (rank[u] == rank[v]) ++rank[v]; } }; const int MAX_N = 2500 + 1; vector<int> row_conds[MAX_N][MAX_N]; vector<int> col_conds[MAX_N][MAX_N]; pii row_range[MAX_N][MAX_N]; // in the same row pii col_range[MAX_N][MAX_N]; // in the same col ll count_rectangles(vector<vector<int>> a) { int n = a.size(); int m = a[0].size(); memset(row_range, -1, sizeof row_range); memset(col_range, -1, sizeof col_range); for (int i=1; i+1<n; ++i) { vector<pii> st; for (int j=0; j<m; ++j) { while (!st.empty() && st.back().first < a[i][j]) { row_range[i][st.back().second].second = j-1; st.pop_back(); } st.push_back({ a[i][j], j }); } st.clear(); for (int j=m-1; j>=0; --j) { while (!st.empty() && st.back().first < a[i][j]) { row_range[i][st.back().second].first = j+1; st.pop_back(); } st.push_back({ a[i][j], j }); } } for (int i=1; i+1<m; ++i) { vector<pii> st; for (int j=0; j<n; ++j) { while (!st.empty() && st.back().first < a[j][i]) { col_range[st.back().second][i].second = j-1; st.pop_back(); } st.push_back({ a[j][i], j }); } st.clear(); for (int j=n-1; j>=0; --j) { while (!st.empty() && st.back().first < a[j][i]) { col_range[st.back().second][i].first = j+1; st.pop_back(); } st.push_back({ a[j][i], j }); } } for (int i=1; i+1<n; ++i) { for (int j=1; j+1<m; ++j) { auto[a, b] = row_range[i][j]; if (a != -1 && b != -1) row_conds[a][b].push_back(i); } } for (int j=1; j+1<m; ++j) { for (int i=1; i+1<n; ++i) { auto[c, d] = col_range[i][j]; if (c != -1 && d != -1) col_conds[c][d].push_back(j); } } for (int i=0; i<MAX_N; ++i) { for (int j=i; j<MAX_N; ++j) { row_conds[i][j].erase(unique(row_conds[i][j].begin(), row_conds[i][j].end()), row_conds[i][j].end()); col_conds[i][j].erase(unique(col_conds[i][j].begin(), col_conds[i][j].end()), col_conds[i][j].end()); } } DisjointSet dsu(n*m); for (int i=1; i+1<n; ++i) { for (int j=1; j+1<m; ++j) { if (i+2 < n) { if (row_range[i][j] == row_range[i+1][j] && col_range[i][j] == col_range[i+1][j]) dsu.merge(i*m+j, (i+1)*m+j); } if (j+2 < m) { if (row_range[i][j] == row_range[i][j+1] && col_range[i][j] == col_range[i][j+1]) dsu.merge(i*m+j, i*m+j+1); } } } ll ans = 0; for (int i=1; i+1<n; ++i) { for (int j=1; j+1<m; ++j) { if (i*m+j == dsu.find(i*m+j)) { auto[a, b] = row_range[i][j]; auto[c, d] = col_range[i][j]; if (a != -1 && b != -1 && c != -1 && d != -1) { auto row_lb = lower_bound(row_conds[a][b].begin(), row_conds[a][b].end(), c); auto row_ub = lower_bound(row_conds[a][b].begin(), row_conds[a][b].end(), d); auto col_lb = lower_bound(col_conds[c][d].begin(), col_conds[c][d].end(), a); auto col_ub = lower_bound(col_conds[c][d].begin(), col_conds[c][d].end(), b); // cout << i << ' ' << j << ' ' << *row_lb << ' ' << *row_ub << ' ' << *col_lb << ' ' << *col_ub << endl; if (*row_lb == c && *row_ub == d && row_ub-row_lb == d-c && *col_lb == a && *col_ub == b && col_ub-col_lb == b-a) 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...