제출 #288819

#제출 시각아이디문제언어결과실행 시간메모리
288819amiratouRectangles (IOI19_rect)C++14
0 / 100
156 ms59164 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define sz(x) (int)(x.size()) typedef long long ll; const int MX = 2505; int cl[MX][MX]; // smallest row>i on same column containing one int nxt[MX][MX]; // furthest col on same row tel que same close int cum[MX][MX]; // normal cum on columns int gimme(int col,int a,int b){ return cum[b][col] - (a?cum[a-1][col]:0); } ll count_rectangles(vector<vector<int> > a) { ll ans=0; int n=sz(a),m=sz(a[0]); for (int j = 0; j < m; ++j) { int last=-1; for (int i = n-1; i >= 0; i--) if(a[i][j]){ cl[i][j]=last,last=i; if((i+1) ==cl[i][j])cl[i][j]=-1; } } for (int i = 0; i < n; ++i) for (int j = 0; j < m; ) { if(!a[i][j]){ cum[i][j]=(!a[i][j]); if(i)cum[i][j]+=cum[i-1][j]; nxt[i][j]=-1,j++; continue; } int z=j; while(z<m && cl[i][z]==cl[i][j]) z++; for (int A = j; A < z; ++A){ cum[i][A]=(!a[i][A]); if(i)cum[i][A]+=cum[i-1][A]; nxt[i][A]=z; } j=z; } for (int i = 0; i < n-2; ++i) for (int j = 1; j < m-1; ++j) if(a[i][j] && cl[i][j]!=-1 && !gimme(j-1,i+1,cl[i][j]-1) && !gimme(nxt[i][j],i+1,cl[i][j]-1)) 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...