제출 #170713

#제출 시각아이디문제언어결과실행 시간메모리
170713youngyojunRectangles (IOI19_rect)C++17
100 / 100
4386 ms747564 KiB
#include "rect.h" #include <bits/stdc++.h> #define eb emplace_back #define sz(V) ((int)(V).size()) #define allv(V) ((V).begin()),((V).end()) #define sorv(V) sort(allv(V)) #define univ(V) (V).erase(unique(allv(V)),(V).end()) #define upmin(a,b) (a)=min((a),(b)) #define upmax(a,b) (a)=max((a),(b)) #define fi first #define se second #define INF (0x3f3f3f3f) using namespace std; typedef pair<int, int> pii; struct NOD { NOD(int sy, int sx, int ey, int ex) : sy(sy), sx(sx), ey(ey), ex(ex) {} int sy, sx, ey, ex; void f(int &_sy, int &_sx, int &_ey, int &_ex) const { _sy = sy; _sx = sx; _ey = ey; _ex = ex; } bool operator < (const NOD &t) const { if(sy != t.sy) return sy < t.sy; if(sx != t.sx) return sx < t.sx; if(ey != t.ey) return ey < t.ey; return ex < t.ex; } bool operator == (const NOD &t) const { return sy == t.sy && sx == t.sx && ey == t.ey && ex == t.ex; } }; const int MX = 4096; struct SEG { SEG() { init(); } int d[MX*2]; void init() { fill(d, d+MX*2, INF); } void upd(int x, int r) { upmin(d[x+MX], r); } void cal() { for(int i = MX; i--;) d[i] = min(d[i<<1], d[i<<1|1]); } int get(int s, int e) { int r = INF; for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) { if(s&1) upmin(r, d[s++]); if(~e&1) upmin(r, d[e--]); } return r; } } segu[2505], segd[2505], segl[2505], segr[2505]; vector<NOD> NV; int myu[2505][2505], myd[2505][2505], myl[2505][2505], myr[2505][2505]; int cou[2505][2505], cod[2505][2505], col[2505][2505], cor[2505][2505]; int A[2505][2505]; int H, W, Ans; int solve() { for(int j = 0; j < W; j++) { vector<pii> V; V.eb(-1, INF); for(int i = 0, h; i < H; i++) { for(h = A[i][j]; V.back().se <= h; V.pop_back()); myu[i][j] = V.back().fi; V.eb(i, h); } V.clear(); V.eb(H, INF); for(int i = H, h; i--;) { for(h = A[i][j]; V.back().se <= h; V.pop_back()); myd[i][j] = V.back().fi; V.eb(i, h); } V.clear(); V.eb(-1, INF); for(int i = 0, h; i < H; i++) { for(h = A[i][j]; V.back().se < h; V.pop_back()); cou[i][j] = V.back().fi + 1; V.eb(i, h); } V.clear(); V.eb(H, INF); for(int i = H, h; i--;) { for(h = A[i][j]; V.back().se < h; V.pop_back()); cod[i][j] = V.back().fi - 1; V.eb(i, h); } } for(int i = 0; i < H; i++) { vector<pii> V; V.eb(-1, INF); for(int j = 0, h; j < W; j++) { for(h = A[i][j]; V.back().se <= h; V.pop_back()); myl[i][j] = V.back().fi; V.eb(j, h); } V.clear(); V.eb(W, INF); for(int j = W, h; j--;) { for(h = A[i][j]; V.back().se <= h; V.pop_back()); myr[i][j] = V.back().fi; V.eb(j, h); } V.clear(); V.eb(-1, INF); for(int j = 0, h; j < W; j++) { for(h = A[i][j]; V.back().se < h; V.pop_back()); col[i][j] = V.back().fi + 1; V.eb(j, h); } V.clear(); V.eb(W, INF); for(int j = W, h; j--;) { for(h = A[i][j]; V.back().se < h; V.pop_back()); cor[i][j] = V.back().fi - 1; V.eb(j, h); } } for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) { segu[i].upd(j, -cou[i][j]); segd[i].upd(j, cod[i][j]); segl[j].upd(i, -col[i][j]); segr[j].upd(i, cor[i][j]); } for(int i = 0; i < H; i++) { segu[i].cal(); segd[i].cal(); } for(int i = 0; i < W; i++) { segl[i].cal(); segr[i].cal(); } for(int i = 1; i < H-1; i++) for(int j = 1; j < W-1; j++) { int sy = myu[i][j] + 1, sx = myl[i][j] + 1, ey = myd[i][j] - 1, ex = myr[i][j] - 1; if(!sy || !sx || H-1 == ey || W-1 == ex) continue; NV.eb(sy, sx, ey, ex); } sorv(NV); univ(NV); for(auto &hubo : NV) { int sy, sx, ey, ex; hubo.f(sy, sx, ey, ex); if(sy < -segu[ey+1].get(sx, ex)) continue; if(segd[sy-1].get(sx, ex) < ey) continue; if(sx < -segl[ex+1].get(sy, ey)) continue; if(segr[sx-1].get(sy, ey) < ex) continue; Ans++; } return Ans; } long long count_rectangles(std::vector<std::vector<int> > a) { ::H = sz(a); ::W = sz(a[0]); for(int i = 0; i < ::H; i++) for(int j = 0; j < ::W; j++) ::A[i][j] = a[i][j]; return solve(); }
#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...