# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
428183 | Ahmadsm2005 | Rectangles (IOI19_rect) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rect.h"
//#include "grader.cpp"
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>>RE(2501);
vector<vector<pair<int,int>>>RE2(2501);
int sparseR[2501][2501][12],sparseC[2501][2501][12],n,m,LOG[2501];
map<pair<int,int>,int>lol[701];
vector<vector<int>>A;
bool DP[701][701][701];
void BUILD(){
for(int i=0;i<n;i++)
for(int l=0;l<m;l++)
sparseR[i][l][0]=A[i][l];
for(int i=0;i<n;i++)
for(int l=0;l<m;l++)
sparseC[l][i][0]=A[i][l];
for(int i=0;i<n;i++){
for(int x=1;x<12;x++){
for(int l=0;l+(1<<(x))<=m;l++){
sparseR[i][l][x]=max(sparseR[i][l][x-1],sparseR[i][l+(1<<(x-1))][x-1]);
}
}
}
for(int i=0;i<m;i++){
for(int x=1;x<12;x++){
for(int l=0;l+(1<<(x))<=n;l++){
sparseC[i][l][x]=max(sparseC[i][l][x-1],sparseC[i][l+(1<<(x-1))][x-1]);
}
}
}
}
/*int queryRz(int X1,int X2,int Y){
int DIFF=LOG[X2-X1+1];
return max(sparseR[Y][X1][DIFF],sparseR[Y][X2-(1<<DIFF)+1][DIFF]);
}
int queryCz(int Y1,int Y2,int X){
return max(sparseC[X][Y1][LOG[Y2-Y1+1]],sparseC[X][Y2-(1<<DIFF)+1][LOG[Y2-Y1+1]]);
}*/
bool check(int x1,int x2,int y1,int y2){
int F=max(sparseC[i][x1][LOG[x2-x1+1]],sparseC[i][x2-(1<<LOG[x2-x1+1])+1][LOG[x2-x1+1]]);
if((F>=A[x1-1][i])||(F>=A[x2+1][i]))
return 0;
return 1;
}
bool check2(int x1,int x2,int y1,int y2){
int F=max(sparseR[i][y1][LOG[y2-y1+1]],sparseR[i][y2-(1<<LOG[y2-y1+1])+1][LOG[y2-y1+1]]);
if((F>=A[i][y1-1])||(F>=A[i][y2+1]))
return 0;
return 1;
}
long long count_rectangles(vector<vector<int>>a){
LOG[1]=0;
for(int i=2;i<=2500;i++)
LOG[i]=LOG[i/2]+1;
A=a;
n=a.size(),m=a[0].size();
BUILD();
for(int i=1;i<n-1;i++){
for(int l=1;l<m-1;l++){
for(int x=l;x<m-1;x++){
if(check2(i,i,l,x)){
RE[i].push_back({l,x}),lol[i].insert({{l,x},RE[i].size()-1});
}
}
}
}
for(int i=1;i<m-1;i++){
for(int l=1;l<n-1;l++){
for(int x=l;x<n-1;x++){
if(check(l,x,i,i)){
RE2[i].push_back({l,x});
}
}
}
}
int CNT=0;
for(int i=1;i<n-1;i++){
for(int x=0;x<RE[i].size();x++){
for(int l=i;l<n-1;l++){
if(!check2(l,l,RE[i][x].first,RE[i][x].second))
break;
DP[i][l][x]=1;
}
}
}
for(int i=1;i<m-1;i++){
for(int x=0;x<RE2[i].size();x++){
for(int l=i;l<m-1;l++){
if(!check(RE2[i][x].first,RE2[i][x].second,l,l))
break;
if(lol[RE2[i][x].first].find({i,l})==lol[RE2[i][x].first].end()){
continue;
}
if(DP[RE2[i][x].first][RE2[i][x].second][lol[RE2[i][x].first].at({i,l})]){
CNT++;
}
}
}
}
return CNT;
}