제출 #1225375

#제출 시각아이디문제언어결과실행 시간메모리
1225375Hamed_GhaffariRectangles (IOI19_rect)C++20
100 / 100
1795 ms756140 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; using ll = long long; #define ii int32_t #define int int16_t using pii = pair<int, int>; #define X first #define Y second const int MXN = 2501; int n, m; vector<pii> vr[MXN][MXN], vd[MXN][MXN]; int L[MXN][MXN], R[MXN][MXN]; int stk[MXN], szx, ord[MXN]; int fen[MXN]; inline void updx(int p, int x) { for(++p; p<=m; p+=p&-p) fen[p] += x; } inline int getx(int p) { int res=0; for(++p; p; p-=p&-p) res += fen[p]; return res; } ll count_rectangles(vector<vector<ii>> a) { n = a.size(), m = a[0].size(); if(n<=2 || m<=2) return 0; for(int l=0; l<m; l++) for(int r=l; r<m; r++) L[l][r] = n+5; for(int i=n-2; i>=1; i--) { szx = 0; for(int j=m-1; j>=0; j--) { while(szx && a[i][stk[szx-1]]<a[i][j]) { if(j+1<stk[szx-1]) vr[i][j+1].push_back({stk[szx-1]-1, 0}); szx--; } if(szx) { if(j+1<stk[szx-1]) vr[i][j+1].push_back({stk[szx-1]-1, 0}); if(a[i][stk[szx-1]]==a[i][j]) szx--; } stk[szx++] = j; } for(int l=1, sz; l+1<m; l++) { sz = vr[i][l].size(); for(int j=0, r; j<sz; j++) { r = vr[i][l][j].X; if(L[l][r]==i+1) { vr[i][l][j].Y = R[l][r]; L[l][r] = i; } else vr[i][l][j].Y = L[l][r] = R[l][r] = i; } } } for(int l=0; l<n; l++) for(int r=l; r<n; r++) L[l][r] = m+5; for(int j=m-2; j>=1; j--) { szx = 0; for(int i=n-1; i>=0; i--) { while(szx && a[stk[szx-1]][j]<a[i][j]) { if(i+1<stk[szx-1]) vd[i+1][j].push_back({stk[szx-1]-1, 0}); szx--; } if(szx) { if(i+1<stk[szx-1]) vd[i+1][j].push_back({stk[szx-1]-1, 0}); if(a[stk[szx-1]][j]==a[i][j]) szx--; } stk[szx++] = i; } for(int l=1, sz; l+1<n; l++) { sz = vd[l][j].size(); for(int i=0, r; i<sz; i++) { r = vd[l][j][i].X; if(L[l][r]==j+1) { vd[l][j][i].Y = R[l][r]; L[l][r] = j; } else vd[l][j][i].Y = L[l][r] = R[l][r] = j; } } } ll ans = 0; for(int i=0, sr, sd; i<n; i++) for(int j=0; j<m; j++) { sr = vr[i][j].size(); sd = vd[i][j].size(); iota(ord, ord+sr, 0); sort(ord, ord+sr, [&](int x, int y) { return vr[i][j][x].Y<vr[i][j][y].Y; }); int p1=0, p2=0; while(p1<sr && p2<sd) { if(vd[i][j][p2].X<=vr[i][j][ord[p1]].Y) updx(vd[i][j][p2++].Y, 1); else ans += p2-getx(vr[i][j][ord[p1++]].X-1); } while(p1<sr) ans += p2-getx(vr[i][j][ord[p1++]].X-1); while((--p2)>=0) updx(vd[i][j][p2].Y, -1); } 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...