Submission #1290813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290813		lambd47	Rectangles (IOI19_rect)	C++20	0 / 100	2817 ms	620 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

    L(j,1,m-2){
        //olhando pra fila j
        vector<int> fila;
        L(i,0,n-1){
            while(!fila.empty() && vec[fila.back()][j]<vec[i][j]){
                dwn[fila.back()][j]=i;
                fila.pop_back();
            }
            if(!fila.empty()){
                up[i][j]=fila.back();
            }
            fila.push_back(i);
        }
    }

    vector<vector<int>> lef(n,vector<int> (m,-1));
    vector<vector<int>> rig(n,vector<int> (m,MOD));//mod
    L(i,1,n-2){
        vector<int> fila;
        L(j,0,m-1){
            while(!fila.empty() && vec[i][fila.back()]<vec[i][j]){
                rig[i][fila.back()]=j;
                fila.pop_back();
            }
            if(!fila.empty()){
                lef[i][j]=fila.back();
            }
            fila.push_back(j);
        }
    }
    /*
    L(i,0,n-1){
        L(j,0,m-1){
            cout<<rig[i][j]<<" ";
        }
        cout<<"\n";
    }
    */

    int 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){
                        L(j,c,d){
                            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: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28