Submission #368142

#	Time	Username	Problem	Language	Result	Execution time	Memory
368142		leinad2	Rectangles (IOI19_rect)	C++17	37 / 100	5066 ms	34028 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;
long long count_rectangles(vector<vector<int> > a)
{
    int n=a.size();
    int m=a[0].size();
    int i, j, k, l;
    long long ans=0;
    vector<pair<int, int> >v[2510];
    map<pair<int, int>, vector<int> >mp;
    for(i=1;i<n-1;i++)
    {
        for(j=0;j<m;j++)
        {
            l=-1;
            for(k=j+1;k<m;k++)
            {
                if(k>j+1)
                {
                    if(a[i][j]>l&&a[i][k]>l)
                    {
                        v[i].push_back({j, k});
                    }
                }
                l=max(l, a[i][k]);
            }
        }
    }
    for(j=1;j<m-1;j++)
    {
        for(i=0;i<n;i++)
        {
            l=-1;
            for(k=i+1;k<n;k++)
            {
                if(k>i+1)
                {
                    if(a[i][j]>l&&a[k][j]>l)
                    {
                        mp[{i, k}].push_back(j);
                    }
                }
                l=max(l, a[k][j]);
            }
        }
    }
    for(i=1;i<n-1;i++)
    {
        map<pair<int, int>, int>mp2;
        map<pair<int, int>, int>::iterator it;
        for(j=i;j<n-1;j++)
        {
            if(j==i)
            {
                for(k=0;k<v[i].size();k++)
                {
                    mp2[v[i][k]]++;
                }
            }
            else
            {
                map<pair<int, int>, int>mp3;
                for(k=0;k<v[j].size();k++)
                {
                    if(mp2.find(v[j][k])!=mp2.end())
                    {
                        mp3[v[j][k]]++;
                    }
                }
                mp2=mp3;
            }
            if(mp2.size()==0)continue;
            vector<int>V=mp[{i-1, j+1}];
            int A[2510]={};
            for(k=0;k<V.size();k++)
            {
                A[V[k]]++;
            }
            for(k=1;k<m;k++)A[k]+=A[k-1];
            for(it=mp2.begin();it!=mp2.end();it++)
            {
                if(A[it->first.second-1]-A[it->first.first]==it->first.second-1-it->first.first)ans++;
            }
        }
    }
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                 for(k=0;k<v[i].size();k++)
      |                         ~^~~~~~~~~~~~
rect.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                 for(k=0;k<v[j].size();k++)
      |                         ~^~~~~~~~~~~~
rect.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             for(k=0;k<V.size();k++)
      |                     ~^~~~~~~~~

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