제출 #229768

#제출 시각아이디문제언어결과실행 시간메모리
229768combi1k1Rectangles (IOI19_rect)C++14
0 / 100
574 ms118184 KiB
//#include "rect.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define ld double #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() #define pb emplace_back #define X first #define Y second const int N = 2e5 + 5; typedef pair<int,int> ii; typedef vector<int> vi; typedef vector<vi> mtx; ll count_rectangles(mtx A) { int n = sz(A); int m = sz(A[0]); mtx l(n,vi(m,-1)); mtx r(n,vi(m,-1)); mtx u(n,vi(m,-1)); mtx d(n,vi(m,-1)); for(int i = 0 ; i < n ; ++i) { stack<int> lef; stack<int> rig; for(int j = 0 ; j < m ; ++j) { while (lef.size() && A[i][lef.top()] < A[i][j]) lef.pop(); if (lef.size()) l[i][j] = lef.top(); lef.push(j); } for(int j = m - 1 ; j >= 0 ; --j) { while (rig.size() && A[i][rig.top()] < A[i][j]) rig.pop(); if (rig.size()) r[i][j] = rig.top(); rig.push(j); } } for(int j = 0 ; j < m ; ++j) { stack<int> lef; stack<int> rig; for(int i = 0 ; i < n ; ++i) { while (lef.size() && A[lef.top()][j] < A[i][j]) lef.pop(); if (lef.size()) u[i][j] = lef.top(); lef.push(i); } for(int i = n - 1 ; i >= 0 ; --i) { while (rig.size() && A[rig.top()][j] < A[i][j]) rig.pop(); if (rig.size()) d[i][j] = rig.top(); rig.push(i); } } mtx LU(n,vi(m,-1)); mtx RU(n,vi(m,-1)); mtx UL(n,vi(m,-1)); mtx DL(n,vi(m,-1)); for(int i = 0 ; i < n ; ++i) for(int j = 0 ; j < m ; ++j) { if (l[i][j] >= 0) { if (i && l[i - 1][j] == l[i][j]) LU[i][j] = LU[i - 1][j]; else if (i && r[i - 1][l[i][j]] == j) LU[i][j] = RU[i - 1][l[i][j]]; else LU[i][j] = i; } if (r[i][j] >= 0) { if (i && r[i - 1][j] == r[i][j]) RU[i][j] = RU[i - 1][j]; else if (i && l[i - 1][r[i][j]] == j) RU[i][j] = LU[i - 1][r[i][j]]; else RU[i][j] = i; } } for(int j = 0 ; j < m ; ++j) for(int i = 0 ; i < n ; ++i) { if (u[i][j] >= 0) { if (j && u[i][j - 1] == u[i][j]) UL[i][j] = UL[i][j - 1]; else if (j && d[u[i][j]][j - 1] == i) UL[i][j] = DL[u[i][j]][j - 1]; else UL[i][j] = j; } if (d[i][j] >= 0) { if (j && d[i][j - 1] == d[i][j]) DL[i][j] = DL[i][j - 1]; else if (j && u[d[i][j]][j - 1] == i) DL[i][j] = UL[d[i][j]][j - 1]; else DL[i][j] = j; } } unordered_set<ll> ans; auto check = [&](int L,int R,int U,int D) { if (L > R || U > D) return; if (L < 1 || R > n - 2) return; if (U < 1 || D > n - 2) return; if (!((r[R][U - 1] == D + 1 && RU[R][U - 1] <= L) || (l[R][D + 1] == U - 1 && LU[R][D + 1] <= L))) return; if (!((d[L - 1][D] == R + 1 && DL[L - 1][D] <= U) || (u[R + 1][D] == L - 1 && UL[R + 1][D] <= U))) return; ll val = L; val *= 3000; val += R; val *= 3000; val += U; val *= 3000; val += D; ans.insert(val); }; for(int i = 1 ; i < n - 1 ; ++i) for(int j = 1 ; j < m - 1 ; ++j) { int R = d[i - 1][j] - 1; if (u[i + 1][j] >= 0 && l[i][j + 1] >= 0) check(u[i + 1][j] + 1,i,l[i][j + 1] + 1,j); if (u[i + 1][j] >= 0 && r[i][j - 1] >= 0) check(u[i + 1][j] + 1,i,j,r[i][j - 1] - 1); if (R < i) continue; if (l[i][j + 1] >= 0) check(i,R,l[i][j + 1] + 1,j); if (r[i][j - 1] >= 0) check(i,R,j,r[i][j - 1] - 1); if (l[R][j + 1] >= 0) check(i,R,l[R][j + 1] + 1,j); if (r[R][j - 1] >= 0) check(i,R,j,r[R][j - 1] - 1); } return ans.size(); }
#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...