Submission #823193

#	Time	Username	Problem	Language	Result	Execution time	Memory
823193		vjudge1	Rectangles (IOI19_rect)	C++14	13 / 100	523 ms	104464 KiB

rect

#include<bits/stdc++.h>
#include "rect.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 2500, M = 2500 ;
int pref[N + 1][M + 1], mt[N + 1][M + 1] ;
bool us[N + 1][M + 1] ;
int get_sum(int x1, int y1, int x2, int y2)
{
    return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1] ;
}
ll count_rectangles(vector<vector<int>> v)
{
    bool flag1 = 0 ;
    ll ans = 0 ;
    int n = v.size(), m = v[0].size() ;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m ; j++)
            if(v[i][j] > 1)flag1 = 1 ;
    if(!flag1)
    {
        for(int i = 1 ; i <= n ; i++)
            for(int j = 1 ; j <= m ; j++)
                mt[i][j] = v[i - 1][j - 1] ;
        for(int i = 1 ; i <= n ; i++)
        {
            int now = 0 ;
            for(int j = 1 ; j <= m ; j++)
            {
                now += mt[i][j] ;
                pref[i][j] = pref[i - 1][j] + now ;
            }
        }
        for(int i = 1 ; i <= n ; i++)
            for(int j = 1 ; j <= m ; j++)
            {
                if(mt[i][j])
                    continue ;
                int l = 0, r = j, x1 = i, y1 = j, x2 = i, y2 = j ;
                while(l + 1 < r)
                {
                    int mid = (l + r) / 2 ;
                    if(get_sum(i, mid, i, j))
                        l = mid ;
                    else
                        r = mid ;
                }
                y1 = r ;
                l = j, r = m + 1 ;
                while(l + 1 < r)
                {
                    int mid = (l + r) / 2 ;
                    if(get_sum(i, j, i, mid))
                        r = mid ;
                    else
                        l = mid ;
                }
                y2 = l ;
                l = 0, r = i ;
                while(l + 1 < r)
                {
                    int mid = (l + r) / 2 ;
                    if(get_sum(mid, j, i, j))
                        l = mid ;
                    else
                        r = mid ;
                }
                x1 = r ;
                l = i, r = n + 1 ;
                while(l + 1 < r)
                {
                    int mid = (l + r) / 2 ;
                    if(get_sum(i, j, mid, j))
                        r = mid ;
                    else
                        l = mid ;
                }
                x2 = l ;
                if(x1 > 1 && x1 < n && x2 > 1 && x2 < n && y1 > 1 && y1 < m && y2 > 1 && y2 < m && !get_sum(x1, y1, x2, y2) && get_sum(x1 - 1, y1, x2 + 1, y2) == (y2 - y1 + 1) * 2 && get_sum(x1, y1 - 1, x2, y2 + 1) == (x2 - x1 + 1) * 2 && !us[x1][y1])
                {
                    us[x1][y1] = 1 ;
                    ans++ ;
                }
            }
        return ans ;
    }
    if(n <= 200 && m <= 200 || n <= 3)
    {
        int mx_str[n][m][m] = {}, mx_stl[m][n][n] = {} ;
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < m ; j++)
            {
                int now = 0 ;
                for(int q = j ; q < m ; q++)
                    now = max(now, (int)v[i][q]), mx_str[i][j][q] = now ;
            }
        for(int i = 0 ; i < m ; i++)
            for(int j = 0 ; j < n ; j++)
            {
                int now = 0 ;
                for(int q = j ; q < n ; q++)
                    now = max(now, (int)v[q][i]), mx_stl[i][j][q] = now ;
            }
        for(int x1 = 1 ; x1 < n - 1 ; x1++)
            for(int y1 = 1 ; y1 < m - 1 ; y1++)
                for(int x2 = x1 ; x2 < n - 1 ; x2++)
                {
                    if(v[x1 - 1][y1] <= v[x2][y1])
                        break ;
                    for(int y2 = y1 ; y2 < m - 1 ; y2++)
                    {
                        if(v[x1][y1 - 1] <= v[x1][y2])
                            break ;
                        bool flag = 1 ;
                        for(int i = x1 ; i <= x2 ; i++)
                            if(mx_str[i][y1][y2] >= min(v[i][y1 - 1], v[i][y2 + 1]))
                            {
                                flag &= 0 ;
                                break ;
                            }
                        if(!flag)
                            break ;
                        for(int i = y1 ; i <= y2 ; i++)
                            if(mx_stl[i][x1][x2] >= min(v[x1 - 1][i], v[x2 + 1][i]))
                            {
                                flag &= 0 ;
                                break ;
                            }
                        if(flag)
                            ans += flag ;
                    }
                }
        return ans ;
    }
    if(n <= 200 && m <= 200)
    {
        return ans ;
    }
    return ans ;
}
//signed main()
//{
//    ios_base::sync_with_stdio( 0 ) ;
//    cin.tie( 0 ) ;
//    cout.tie( 0 ) ;
//    int n, m ;
//    cin >> n >> m ;
//    vector<vector<int>> v ;
//    for(int i = 0 ; i < n ; i++)
//    {
//        vector<int> abu ;
//        for(int j = 0 ; j < m ; j++)
//        {
//            int num ;
//            cin >> num ;
//            abu.push_back(num) ;
//        }
//        v.push_back(abu) ;
//    }
//    cout << count_rectangles(v) ;
//    return 0 ;
//}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:89:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   89 |     if(n <= 200 && m <= 200 || n <= 3)
      |        ~~~~~~~~~^~~~~~~~~~~

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