Submission #289363

#	Time	Username	Problem	Language	Result	Execution time	Memory
289363		DanerZein	Rectangles (IOI19_rect)	C++14	28 / 100	5063 ms	364152 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) {
  //cout<<"llamado\n";
  long long c=0;
  if((a.size()<=200 and b.size()<=200) or (a.size()<=3 and b.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]){
	    int n=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++){
      cout<<ud[i].frst.frst<<" "<<ud[i].frst.scnd<<" "<<ud[i].scnd.frst<<" "<<ud[i].scnd.scnd<<endl;
    }
    cout<<endl;
    for(int i=0;i<lr.size();i++){
      cout<<lr[i].frst.frst<<" "<<lr[i].frst.scnd<<" "<<lr[i].scnd.frst<<" "<<lr[i].scnd.scnd<<endl;
    }
    cout<<endl;*/
    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 sw=1;
	if(sw==1){
	int row=(b-t)-1,to=t+1;
	//	cout<<t<<" "<<b<<" "<<l<<" "<<r<<endl;
	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(row==0) {
	  // cout<<i<<" "<<j<<endl;
	  c++;
	}
	}
      }
    }
  }
  else{
    memset(vis,0,sizeof vis);
    b=a;
    // cout<<"else\n";
    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);
	  //cout<<i<<" "<<j<<" "<<sw1<<endl;
	  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:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=1;i<a[0].size()-1;i++){
      |                 ~^~~~~~~~~~~~~~
rect.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |       for(int j=0;j<a.size()-1;j++){
      |                   ~^~~~~~~~~~~
rect.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int k=j+2;k<a.size();k++){
      |                ~^~~~~~~~~
rect.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=1;i<a.size()-1;i++){
      |                 ~^~~~~~~~~~~
rect.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |       for(int j=0;j<a[0].size()-1;j++){
      |                   ~^~~~~~~~~~~~~~
rect.cpp:56:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int k=j+2;k<a[0].size();k++){
      |                ~^~~~~~~~~~~~
rect.cpp:58:10: warning: unused variable 'n' [-Wunused-variable]
   58 |      int n=k;
      |          ^
rect.cpp:73: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]
   73 |     for(int i=0;i<ud.size();i++){
      |                 ~^~~~~~~~~~
rect.cpp:75: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]
   75 |       for(int j=i;j<ud.size();j++){
      |                   ~^~~~~~~~~~
rect.cpp:87:15: 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]
   87 |  for(int k=0;k<lr.size();k++){
      |              ~^~~~~~~~~~
rect.cpp:107:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i=1;i<a.size()-1;i++){
      |                 ~^~~~~~~~~~~
rect.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |       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