제출 #296661

#제출 시각아이디문제언어결과실행 시간메모리
296661ChrisTRectangles (IOI19_rect)C++17
25 / 100
5098 ms773992 KiB
#include <bits/stdc++.h> #include "rect.h" using namespace std; const int MN = 1e5+5; inline long long hsh (int a, int b, int c, int d) { if (c < 0 || c > 1e8 || d < 0 || d > 1e8) return -1; if (c < a) swap(a,c); if (d < b) swap(b,d); return ((long long)a << 36) | ((long long)b << 24) | ((long long)c << 12) | ((long long)d); } long long count_rectangles (vector<vector<int>> a) { int n = a.size(), m = a[0].size(); vector<vector<int>> nextLeft(n,vector<int>(m,1e9)), nextRight(n,vector<int>(m,-1)), nextUp(n,vector<int>(m,1e9)), nextDown(n,vector<int>(m,-1)), upFromLeft(n,vector<int>(m)),upFromRight(n,vector<int>(m)),leftFromDown(n,vector<int>(m)),leftFromUp(n,vector<int>(m)); for (int i = 0; i < n; i++) { vector<int> stk; for (int j = 0; j < m; j++) { while (!stk.empty() && a[i][stk.back()] < a[i][j]) stk.pop_back(); if (!stk.empty()) { nextLeft[i][j] = stk.back(); upFromLeft[i][j] = 1; if (i > 0 && nextLeft[i-1][j] == nextLeft[i][j]) upFromLeft[i][j] += upFromLeft[i-1][j]; else if (i > 0 && nextRight[i-1][stk.back()] == j) upFromLeft[i][j] += upFromRight[i-1][stk.back()]; } stk.push_back(j); } stk.clear(); for (int j = m-1; j >= 0; j--) { while (!stk.empty() && a[i][stk.back()] < a[i][j]) stk.pop_back(); if (!stk.empty()) { nextRight[i][j] = stk.back(); upFromRight[i][j] = 1; if (i > 0 && nextRight[i-1][j] == nextRight[i][j]) upFromRight[i][j] += upFromRight[i-1][j]; else if (i > 0 && nextLeft[i-1][stk.back()] == j) upFromRight[i][j] += upFromLeft[i-1][stk.back()]; } stk.push_back(j); } } for (int j = 0; j < m; j++) { vector<int> stk; for (int i = 0; i < n; i++) { while (!stk.empty() && a[stk.back()][j] < a[i][j]) stk.pop_back(); if (!stk.empty()) { nextUp[i][j] = stk.back(); leftFromUp[i][j] = 1; if (j > 0 && nextUp[i][j-1] == nextUp[i][j]) leftFromUp[i][j] += leftFromUp[i][j-1]; else if (j > 0 && nextDown[stk.back()][j-1] == i) leftFromUp[i][j] += leftFromDown[stk.back()][j-1]; } stk.push_back(i); } stk.clear(); for (int i = n-1; i >= 0; i--) { while (!stk.empty() && a[stk.back()][j] < a[i][j]) stk.pop_back(); if (!stk.empty()) { nextDown[i][j] = stk.back(); leftFromDown[i][j] = 1; if (j > 0 && nextDown[i][j-1] == nextDown[i][j]) leftFromDown[i][j] += leftFromDown[i][j-1]; else if (j > 0 && nextUp[stk.back()][j-1] == i) leftFromDown[i][j] += leftFromUp[stk.back()][j-1]; } stk.push_back(i); } } auto works = [&] (int bx, int ry, int tx, int ly) { return ((nextLeft[bx-1][ry] == ly && bx - upFromLeft[bx-1][ry] <= tx + 1) || (nextRight[bx-1][ly] == ry && bx - upFromRight[bx-1][ly] <= tx + 1)) && ((nextUp[bx][ry-1] == tx && ry - leftFromUp[bx][ry-1] <= ly + 1) || (nextDown[tx][ry-1] == bx && ry - leftFromDown[tx][ry-1] <= ly + 1)); }; auto ok = [&] (int x, int y) {return x >= 0 && x < n && y >= 0 && y <= m;}; int ret = 0; vector<long long> can; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (i > 0 && j > 0 && ok(nextUp[i][j-1],nextLeft[i-1][j])) can.emplace_back(hsh(i,j,nextUp[i][j-1],nextLeft[i-1][j])), can.emplace_back(hsh(i,j,nextUp[i][j-1],nextLeft[nextUp[i][j-1]+1][j])); if (i > 0 && j+1 < m && ok(nextUp[i][j+1],nextRight[i-1][j])) can.emplace_back(hsh(i,j,nextUp[i][j+1],nextRight[i-1][j])), can.emplace_back(hsh(i,j,nextUp[i][j+1],nextRight[nextUp[i][j+1]+1][j])); if (i+1 < n && j > 0 && ok(nextDown[i][j-1],nextLeft[i+1][j])) can.emplace_back(hsh(i,j,nextDown[i][j-1],nextLeft[i+1][j])), can.emplace_back(hsh(i,j,nextDown[i][j-1],nextLeft[nextDown[i][j-1]-1][j])); if (i+1 < n && j+1 < m && ok(nextDown[i][j+1],nextRight[i+1][j])) can.emplace_back(hsh(i,j,nextDown[i][j+1],nextRight[i+1][j])), can.emplace_back(hsh(i,j,nextDown[i][j+1],nextRight[nextDown[i][j+1]-1][j])); } } sort(can.begin(),can.end()); can.erase(unique(can.begin(),can.end()),can.end()); for (long long &h : can) if (~h) { int tx = h >> 36, ly = (h >> 24) & 0xfff, bx = (h >> 12) & 0xfff, ry = h & 0xfff; if (abs(bx - tx) <= 1 || abs(ly - ry) <= 1) continue; for (int i : {bx,tx,ly,ry}) if (i < 0 || i > 1e8) goto fail; ret += works(bx,ry,tx,ly); fail:; } return ret; }
#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...