Submission #289612

#	Time	Username	Problem	Language	Result	Execution time	Memory
289612		DanerZein	Rectangles (IOI19_rect)	C++14	50 / 100	5052 ms	360972 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define frst first
#define scnd second
using namespace std;
#define MAX 1000000000
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<ii,ii> iii;
typedef vector<ii> vii;
vector<vi> b;
int vis[2510][2510];
int Y[4]={-1,0,1,0};
int X[4]={0,-1,0,1};
int c1,r1,c2,r2;
bool sw1=0;
int flod(int y,int x){
  //cout<<y<<" "<<x<<endl;
  c1=min(c1,x);
  r1=min(r1,y);
  c2=max(c2,x);
  r2=max(r2,y);
  vis[y][x]=1;
  int ans=1;
  for(int i=0;i<4;i++){
    if(y+Y[i]<b.size()-1 and y+Y[i]>=1 and x+X[i]<b[0].size()-1 and x+X[i]>=1){
      if(b[y+Y[i]][x+X[i]]==0 and !vis[y+Y[i]][x+X[i]])
      ans+=flod(y+Y[i],x+X[i]);
    }
    else{
      if(b[y+Y[i]][x+X[i]]==0){
	sw1=1;
      }
    }
  }
  return ans;
}
int ma,u,d,l,r,row,i,j,k;
bool sw=0;
long long count_rectangles(std::vector<std::vector<int> > a) {
  long long c=0;
  if((a.size()<=700 and a[0].size()<=700) or (a.size()<=3 and a[0].size()<=2500)){
    vector<vii> ud,lr;
    ud.resize(a[0].size());
    lr.resize(a.size());
    for( i=1;i<a[0].size()-1;i++){
      for( j=0;j<a.size()-1;j++){
	ma=a[j+1][i];
	for( k=j+2;k<a.size();k++){
	  if(ma<a[j][i] and ma<a[k][i]){
	    ud[i].push_back(ii(j,k));
	  }
	  if(ma>a[j][i]) break;
	  ma=max(ma,a[k][i]);
	}
      }
    }
    for(i=1;i<a.size()-1;i++){
      for( j=0;j<a[0].size()-1;j++){
	 ma=a[i][j+1];
	for(k=j+2;k<a[0].size();k++){
	  if(ma<a[i][j] and ma<a[i][k]){
	    lr[i].push_back(ii(j,k));
	  }
	  if(ma>a[i][j]) break;
	  ma=max(ma,a[i][k]);
	}
      }
    }
    for(i=1;i<ud.size();i++){
      for(auto &v:ud[i]){
	u=v.frst; d=v.scnd;
	l=i-1; r=i+1;
	for( j=i;ud.size();j++){
	  sw=0;
	  if(j!=i){
	    for(auto &x:ud[j]){
	      if(u==x.frst and d==x.scnd){
		sw=1;
		break;
	      }
	      if(u<x.first) break;
	    }
	    if(sw==0) break;
	    else r=j+1;
	  }
	   row=(d-u)-1;
	  for( k=u+1;k<lr.size();k++){
	   sw=0;
	    for(auto &x:lr[k]){
	      
	      if(x.first==l and x.second==r){
		sw=1;
		break;
	      }
	      if(l<x.first) break;
	    }
	    if(sw==1) row--;
	    else break;
	    if(row==0) break;
	  }
	  if(row==0) c++;
	}
      }
    }
  }
  else{
    memset(vis,0,sizeof vis);
    b=a;
    for(int i=1;i<a.size()-1;i++){
      for(int j=1;j<a[i].size()-1;j++){
	if(a[i][j]==0 and !vis[i][j]){
	  c1=r1=MAX;
	  c2=r2=-MAX;
	   sw1=0;
	  int ar=flod(i,j);
	  if((abs(c1-c2)+1)*(abs(r1-r2)+1)==ar and sw1==0) c++;
	}
      }
    }
  }
  return c;
}

Compilation message (stderr)

rect.cpp: In function 'int flod(int, int)':
rect.cpp:26:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if(y+Y[i]<b.size()-1 and y+Y[i]>=1 and x+X[i]<b[0].size()-1 and x+X[i]>=1){
      |        ~~~~~~^~~~~~~~~~~
rect.cpp:26:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if(y+Y[i]<b.size()-1 and y+Y[i]>=1 and x+X[i]<b[0].size()-1 and x+X[i]>=1){
      |                                            ~~~~~~^~~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for( i=1;i<a[0].size()-1;i++){
      |              ~^~~~~~~~~~~~~~
rect.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |       for( j=0;j<a.size()-1;j++){
      |                ~^~~~~~~~~~~
rect.cpp:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for( k=j+2;k<a.size();k++){
      |             ~^~~~~~~~~
rect.cpp:58:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(i=1;i<a.size()-1;i++){
      |             ~^~~~~~~~~~~
rect.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |       for( j=0;j<a[0].size()-1;j++){
      |                ~^~~~~~~~~~~~~~
rect.cpp:61:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(k=j+2;k<a[0].size();k++){
      |            ~^~~~~~~~~~~~
rect.cpp:70:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(i=1;i<ud.size();i++){
      |             ~^~~~~~~~~~
rect.cpp:88:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    for( k=u+1;k<lr.size();k++){
      |               ~^~~~~~~~~~
rect.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i=1;i<a.size()-1;i++){
      |                 ~^~~~~~~~~~~
rect.cpp:111:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |       for(int j=1;j<a[i].size()-1;j++){
      |                   ~^~~~~~~~~~~~~~

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