Submission #427650

#	Time	Username	Problem	Language	Result	Execution time	Memory
427650		Ahmadsm2005	Rectangles (IOI19_rect)	C++14	15 / 100	5083 ms	233012 KiB

rect

#include "rect.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>>RE(701);
int sparseR[701][701][10],sparseC[701][701][10],n,m,LOG[701];
vector<vector<int>>A;
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<10;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<10;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 queryR(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 queryC(int Y1,int Y2,int X){
int DIFF=LOG[Y2-Y1+1];
return max(sparseC[X][Y1][DIFF],sparseC[X][Y2-(1<<DIFF)+1][DIFF]);
}
bool check(int x1,int x2,int y1,int y2){
for(int i=x1;i<=x2;i++){
if((queryR(y1,y2,i)>=A[i][y1-1])||(queryR(y1,y2,i)>=A[i][y2+1]))
return 0;
}
for(int i=y1;i<=y2;i++){
if((queryC(x1,x2,i)>=A[x1-1][i])||(queryC(x1,x2,i)>=A[x2+1][i]))
return 0;
}
return 1;
}
bool check2(int x1,int x2,int y1,int y2){
/*for(int i=x1;i<=x2;i++){
for(int l=y1;l<=y2;l++){
if((A[i][y1-1]<=A[i][l])||(A[i][y2+1]<=A[i][l]))
return 0;
}
}*/
for(int i=x1;i<=x2;i++){
if((queryR(y1,y2,i)>=A[i][y1-1])||(queryR(y1,y2,i)>=A[i][y2+1]))
return 0;
}
return 1;
}
long long count_rectangles(vector<vector<int>>a){
LOG[1]=0;
for(int i=2;i<=700;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});
}
}
}
}
long long CNT=0;
set<pair<pair<int,int>,pair<int,int>>>lol;
for(int i=1;i<n-1;i++){
for(int l=1;l<n-1;l++){
for(int x=0;x<RE[i].size();x++){
if(lol.find({{min(i,l),max(l,i)},{RE[i][x].first,RE[i][x].second}})==lol.end())
lol.insert({{min(i,l),max(l,i)},{RE[i][x].first,RE[i][x].second}});
else
continue;
if(check(min(i,l),max(l,i),RE[i][x].first,RE[i][x].second)){
CNT++;
}
}
}
}
return CNT;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:82:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 | for(int x=0;x<RE[i].size();x++){
      |             ~^~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28