Submission #766225

#	Time	Username	Problem	Language	Result	Execution time	Memory
766225		Cyber_Wolf	Rectangles (IOI19_rect)	C++17	25 / 100	5059 ms	28300 KiB

rect

// Problem: P3 - Rectangles
// Contest: DMOJ - IOI '19
// URL: https://dmoj.ca/problem/ioi19p3
// Memory Limit: 1 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
 
using namespace std;
 
mt19937 rng(time(NULL));
 
long long count_rectangles(vector<vector<int>> a)
{
    if(a.size() <= 2)   return 0;
    if(a[0].size() <= 2)    return 0;
	long long ans = 0;
	vector<int> mC(a[0].size()), mR(a.size());
	for(int i = 1; i+1 < a.size(); i++)
	{
	    for(int j = 1; j+1 < a[0].size(); j++)
	    {
	        for(int k = j; k+1 < a[0].size(); k++)  mC[k] = 0;
    	    for(int k = i; k+1 < a.size(); k++)
    	    {
	            for(int z = i; z+1 < a.size(); z++)  mR[z] = 0;
    	        for(int z = j; z+1 < a[0].size(); z++)
    	        {
    	            int f = 0;
    	            for(int l = i; l <= k && (f != 3); l++)
    	            {
		                mR[l] = max(mR[l], a[l][z]);
    	                if(mR[l] >= a[l][j-1])
    	                {
    	                    f |= 3;
    	                }
    	                if(mR[l] >= a[l][z+1])
    	                {
    	                    f |= 1;
    	                }
    	            }
	                mC[z] = max(mC[z], a[k][z]);
    	            for(int l = j; l <= z && (f != 3); l++)
    	            {
    	                if(mC[l] >= a[i-1][l])
    	                {
    	                    f |= 3;
    	                }
    	                if(mC[l] >= a[k+1][l])
    	                {
    	                    f |= 1;
    	                }
    	            }
    	            if(f == 3)  break;
    	            if(f == 1)  continue;
        	        ans++;
        	       // cout << i << ' ' << j << ' ' << k << ' ' << z << '\n';
    	        }
    	    }   
	    }
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 1; i+1 < a.size(); i++)
      |                 ~~~~^~~~~~~~~~
rect.cpp:24:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |      for(int j = 1; j+1 < a[0].size(); j++)
      |                     ~~~~^~~~~~~~~~~~~
rect.cpp:26:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |          for(int k = j; k+1 < a[0].size(); k++)  mC[k] = 0;
      |                         ~~~~^~~~~~~~~~~~~
rect.cpp:27:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |          for(int k = i; k+1 < a.size(); k++)
      |                         ~~~~^~~~~~~~~~
rect.cpp:29:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |              for(int z = i; z+1 < a.size(); z++)  mR[z] = 0;
      |                             ~~~~^~~~~~~~~~
rect.cpp:30:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |              for(int z = j; z+1 < a[0].size(); z++)
      |                             ~~~~^~~~~~~~~~~~~

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