Submission #156304

#TimeUsernameProblemLanguageResultExecution timeMemory
156304wilwxkRectangles (IOI19_rect)C++14
0 / 100
27 ms20896 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=2503; int v[MAXN][MAXN]; short limite[MAXN][MAXN][4]; short seg[4][MAXN][4*MAXN]; int n, m, respf; void histoi() { for(int i=0; i<n; i++) { stack<pair<int, int> > st; for(int j=0; j<m; j++) { while(st.size()&&st.top().first<v[i][j]) st.pop(); limite[i][j][2]= st.size() ? st.top().second : -1; st.push({v[i][j], j}); } while(st.size()) st.pop(); for(int j=m-1; j>=0; j--) { while(st.size()&&st.top().first<v[i][j]) st.pop(); limite[i][j][0]= st.size() ? st.top().second : m; st.push({v[i][j], j}); } } } void histoj() { for(int j=0; j<m; j++) { stack<pair<int, int> > st; for(int i=0; i<n; i++) { while(st.size()&&st.top().first<v[i][j]) st.pop(); limite[i][j][1]= st.size() ? st.top().second : -1; st.push({v[i][j], i}); } while(st.size()) st.pop(); for(int i=n-1; i>=0; i--) { while(st.size()&&st.top().first<v[i][j]) st.pop(); limite[i][j][3]= st.size() ? st.top().second : n; st.push({v[i][j], i}); } } } void junta(int sind, int e, int d, int k, int k2) { if(k==0||k==3) seg[k][k2][sind]=min(seg[k][k2][e], seg[k][k2][e]); else seg[k][k2][sind]=max(seg[k][k2][e], seg[k][k2][e]); } void build(int sind, int ini, int fim, int k, int k2) { if(ini==fim) { if(k==0||k==2) seg[k][k2][sind]=v[ini][k2]; else seg[k][k2][sind]=v[k2][ini]; return; } int mid=(ini+fim)/2; int e=sind*2; int d=e+1; build(e, ini, mid, k, k2); build(d, mid+1, fim, k, k2); junta(sind, e, d, k, k2); } void query(int sind, int ini, int fim, int qini, int qfim, int k, int k2) { if(sind==1) { if(k==0||k==3) seg[k][k2][0]=MAXN; else seg[k][k2][0]=-1; } if(qini<=ini&&qfim>=fim) { junta(0, 0, sind, k, k2); return; } int mid=(ini+fim)/2; int e=sind*2; int d=e+1; if(qini<=mid) query(e, ini, mid, qini, qfim, k, k2); if(qfim>mid) query(d, mid+1, fim, qini, qfim, k, k2); } bool checa(int a, int b, int c, int d) { int i, j, i2, j2; i=min(a, c); i2=max(a, c); j=min(b, d); j2=max(b, d); if(i<0||j<0||i2>n-1||j2>m-1) return 0; // printf("checa %d %d %d %d\n", i, j, i2, j2); query(1, 0, m-1, j+1, j2-1, 3, i); int aa=seg[3][i][0]; if(aa<i2) return 0; query(1, 0, m-1, j+1, j2-1, 1, i2); int bb=seg[1][i2][0]; if(bb>i) return 0; query(1, 0, n-1, i+1, i2-1, 0, j); int cc=seg[0][j][0]; if(cc<j2) return 0; query(1, 0, n-1, i+1, i2-1, 2, j2); int dd=seg[2][j2][0]; if(dd>j) return 0; return 1; } ll count_rectangles(vector< vector<int> > A) { n=A.size(); m=A[0].size(); for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { v[i][j]=A[i][j]; } } histoi(); histoj(); // for(int i=0; i<n; i++) { // for(int j=0; j<m; j++) printf("%d ", limite[i][j][3]); // printf("\n"); // } for(int i=0; i<n; i++) build(1, 0, m-1, 1, i), build(1, 0, m-1, 3, i); for(int j=0; j<m; j++) build(1, 0, n-1, 0, j), build(1, 0, n-1, 2, j); for(int ii=1; ii<n-1; ii++) { for(int jj=1; jj<m-1; jj++) { // printf("%d %d\n", ii, jj); int i=limite[ii][jj][1]; int j=limite[ii][jj][2]; int i2=limite[ii][jj][3]; int j2=limite[ii][jj][0]; respf+=checa(i, j, i2, j2); } } return respf; }
#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...