제출 #299224

#제출 시각아이디문제언어결과실행 시간메모리
299224antimirageRectangles (IOI19_rect)C++14
0 / 100
457 ms311276 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; const int N = (int)7e6 + 7; struct DSU { int par[N], sz[N]; int mnx[N], mxx[N], mny[N], mxy[N]; int sum[N]; DSU() { fill(sz, sz + N, 1); iota(par, par + N, 0); } int getpar(int a) { return (par[a] == a) ? a : par[a] = getpar(par[a]); } void connect(int a, int b) { a = getpar(a); b = getpar(b); if (a != b) { if (sz[a] > sz[b]) swap(a, b); sz[b] += sz[a]; par[a] = b; mnx[b] = min(mnx[b], mnx[a]); mxx[b] = max(mxx[b], mxx[a]); mny[b] = min(mny[b], mny[a]); mxy[b] = max(mxy[b], mxy[a]); sum[b] += sum[a]; } } }dsu; int n, m; int getpos(int x, int y) { return x * m + y; } vector <int> vec[N]; long long count_rectangles(std::vector<std::vector<int> > a) { n = a.size(); m = a[0].size(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dsu.mnx[getpos(i, j)] = dsu.mxx[getpos(i, j)] = i; dsu.mny[getpos(i, j)] = dsu.mxy[getpos(i, j)] = j; dsu.sum[getpos(i, j)] = 4; if (i == 0 || i == n - 1 || j == 0 || j == m - 1) { dsu.sum[getpos(i, j)] = 1e5; } vec[a[i][j]].push_back(getpos(i, j)); } } long long ans = 0; for (int i = 0; i < N; i++) { if (vec[i].empty()) continue; int res = 0; for (int to : vec[i]) { if (to % m != 0) { // y - 1 if (a[to / m][to % m - 1] < i) { dsu.connect(to, to - 1); res++; } else { dsu.sum[to - 1]--; } } if (to % m != m - 1) { // y + 1 if (a[to / m][to % m + 1] < i) { dsu.connect(to, to + 1); res++; } else { dsu.sum[to + 1]--; } } if (to / m > 0) { // x - m if (a[to / m - 1][to % m] < i) { dsu.connect(to, to - m); res++; } else { dsu.sum[to - m]--; } } if (to / m < n - 1) { // x + m if (a[to / m + 1][to % m] < i) { dsu.connect(to, to + m); res++; } else { dsu.sum[to + m]--; } } dsu.sum[dsu.getpar(to)] -= res; } for (int to : vec[i]) { int par = dsu.getpar(to); int sum = dsu.sum[par]; int need = ((dsu.mxx[par] - dsu.mnx[par] + 1) + (dsu.mxy[par] - dsu.mny[par] + 1)) * 2; int area = (dsu.mxx[par] - dsu.mnx[par] + 1) * (dsu.mxy[par] - dsu.mny[par] + 1); if (sum == need && dsu.sz[par] == area) { 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...