Submission #289398

#	Time	Username	Problem	Language	Result	Execution time	Memory
289398		DanerZein	Rectangles (IOI19_rect)	C++14	28 / 100	5097 ms	362148 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;
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;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
  long long c=0;
  if((a.size()<=200 and a[0].size()<=200) or (a.size()<=3 and a[0].size()<=2500)){
    vector<iii> ud,lr;
    for(int i=1;i<a[0].size()-1;i++){
      for(int j=0;j<a.size()-1;j++){
	int ma=a[j+1][i];
	for(int k=j+2;k<a.size();k++){
	  if(ma<a[j][i] and ma<a[k][i]){
	    ud.push_back(iii(ii(j,i),ii(k,i)));
	  }
	  ma=max(ma,a[k][i]);
	}
      }
    }
    for(int i=1;i<a.size()-1;i++){
      for(int j=0;j<a[0].size()-1;j++){
	int ma=a[i][j+1];
	for(int k=j+2;k<a[0].size();k++){
	  if(ma<a[i][j] and ma<a[i][k]){
	    lr.push_back(iii(ii(i,j),ii(i,k)));
	  }
	  ma=max(ma,a[i][k]);
	}
      }
    }
    for(int i=0;i<ud.size();i++){
      int t=ud[i].first.first,l=ud[i].first.second-1,r=ud[i].scnd.scnd+1,b=ud[i].scnd.frst;
      for(int j=i;j<ud.size();j++){
	bool sw=0;
	if(j!=i){
	  if(r==ud[j].scnd.scnd and t==ud[j].frst.frst and b==ud[j].scnd.frst){
	    r=ud[j].scnd.scnd+1;
	    sw=1;
	  }
	  else{
	    if(r<ud[j].scnd.scnd) break;
	  }
	}
	else sw=1;
	if(sw==1){
	  int row=(b-t)-1,to=t+1;
	  for(int k=0;k<lr.size();k++){
	    if(row==0) break;
	    int ta=lr[k].frst.frst,la=lr[k].frst.scnd,ra=lr[k].scnd.scnd;
	    if(to==ta and la==l and ra==r){
	      row--;
	      to++;
	    }
	    if(ta>to) 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:25:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     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:25:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     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:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=1;i<a[0].size()-1;i++){
      |                 ~^~~~~~~~~~~~~~
rect.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |       for(int j=0;j<a.size()-1;j++){
      |                   ~^~~~~~~~~~~
rect.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int k=j+2;k<a.size();k++){
      |                ~^~~~~~~~~
rect.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=1;i<a.size()-1;i++){
      |                 ~^~~~~~~~~~~
rect.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |       for(int j=0;j<a[0].size()-1;j++){
      |                   ~^~~~~~~~~~~~~~
rect.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int k=j+2;k<a[0].size();k++){
      |                ~^~~~~~~~~~~~
rect.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0;i<ud.size();i++){
      |                 ~^~~~~~~~~~
rect.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |       for(int j=i;j<ud.size();j++){
      |                   ~^~~~~~~~~~
rect.cpp:79:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    for(int k=0;k<lr.size();k++){
      |                ~^~~~~~~~~~
rect.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i=1;i<a.size()-1;i++){
      |                 ~^~~~~~~~~~~
rect.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |       for(int j=1;j<a[i].size()-1;j++){
      |                   ~^~~~~~~~~~~~~~

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