Submission #1290832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290832		lambd47	Rectangles (IOI19_rect)	C++20	37 / 100	5094 ms	67728 KiB

rect

#include<bits/stdc++.h>
#include "rect.h"
using namespace std;

#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()

long long count_rectangles(std::vector<std::vector<int> > vec) {
    int n=sz(vec);
    int m=sz(vec[0]);
    const int MOD=1e9+7;
    vector<vector<int>> up(n,vector<int> (m,-1));
    vector<vector<int>> dwn(n,vector<int> (m,MOD));//mod
    vector<vector<int>> lef(n,vector<int> (m,-1));
    vector<vector<int>> rig(n,vector<int> (m,MOD));//mod
                                                   //
                                                   //
                                                   //
    L(i,1,n-2){
        L(j,1,m-2){
            R(k,j-1,0){
                if(vec[i][j]<vec[i][k]){
                    lef[i][j]=k;break;
                }
            }
            L(k,j+1,m-1){
                if(vec[i][j]<vec[i][k]){
                    rig[i][j]=k;break;
                }
            }
            R(k,i-1,0){
                if(vec[i][j]<vec[k][j]){
                    up[i][j]=k;break;
                }
            }
            L(k,i+1,n-1){
                if(vec[i][j]<vec[k][j]){
                    dwn[i][j]=k;break;
                }
            }
        }
    }


   ll resp=0;
    L(a,1,n-2){
        L(b,a,n-2){
            L(c,1,m-2){
                L(d,c,m-2){
                    int ok=1;
                    L(i,a,b){
                        if(ok==0)break;
                        L(j,c,d){
                            if(ok==0)break;
                            if(up[i][j]<a-1 || dwn[i][j]>b+1 || lef[i][j]<c-1 || rig[i][j]>d+1)ok=0;
                        }
                    }
                    resp+=ok;
                }
            }
        }
    }
    return resp;





}

• 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