Submission #280503

#	Time	Username	Problem	Language	Result	Execution time	Memory
280503		CaroLinda	Rectangles (IOI19_rect)	C++14	72 / 100	5116 ms	1048576 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

#define sz(x) (int)x.size()
#define mkt make_tuple
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define eb emplace_back
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define debug printf
#define all(x) x.begin(),x.end()

const int MAXN = 2510 ;

using namespace std ;

int N , M ;

void solve( vector< vector<int > > &grid, vector< vector< vector<pii> > > &toPut )
{

    int tamLinha = sz( grid[0] ) ;
    vector<int> esq(tamLinha) , dir(tamLinha) , getFreq( tamLinha ) , lastVisit(tamLinha) ;

    for(int i = 1 ; i < sz(grid) - 1 ; i++ )
    {

        for(int j = tamLinha - 1 ; j >= 0 ; j-- )
            esq[j] = dir[j] = -1 ;

        set<pii> s ;

        for(int j = tamLinha - 2;  j >= 0 ; j-- )
        {

            int x = j+1 ;

            while( x != -1 && grid[i][x]<= grid[i][j] )
                x = dir[x] ;

            dir[j] = x ;

        }

        for(int j = 1 ; j <  tamLinha ; j++ )
        {

            int x = j-1 ;

            while(x != -1 && grid[i][x] <= grid[i][j] )
                x = esq[x] ;

            esq[j] = x ;

        }

        lp(j,1,tamLinha-1)
            if( esq[j] != -1 && dir[j] != -1 && s.find(mk( esq[j] , dir[j] )) == s.end() )
            {
                toPut[ i ][ esq[j]+1 ].emplace_back( mk(dir[j]-1 , i) ) ;
                s.insert( mk(esq[j] , dir[j]) ) ;
            }

    }

   for(int j = 1 ; j < tamLinha ; j++ )
    {
        lp(i,0,tamLinha) getFreq[i] = lastVisit[i] = -1 ;

        for(int i = sz(grid) - 2 ; i >= 1 ; i-- )
            for(auto &e : toPut[i][j] )
            {
                if(  lastVisit[e.ff] != i+1 ) getFreq[e.ff] = i ;
                e.ss = getFreq[e.ff] ;
                lastVisit[e.ff] = i ;
            }
    }

}

ll count_rectangles( vector<vector<int> > mat )
{
    N = sz(mat) ;
    M = sz( mat[0] ) ;

    vector< vector<int> > gridCerto , gridRota ;
    vector< vector< vector<pii> > > auxCerto, auxRota ;
    lp(i,0,N)
    {
        gridCerto.emplace_back(*(new vector<int>)) ;
        auxCerto.emplace_back(*(new vector< vector<pii> >)) ;
        lp(j,0,M)
        {
            gridCerto[i].emplace_back( mat[i][j] ) ;
            auxCerto[i].emplace_back( *(new vector<pii>) ) ;
        }
    }
    lp(i,0,M)
    {
        gridRota.emplace_back( *(new vector<int>) ) ;
        auxRota.emplace_back(*(new vector< vector<pii> >)) ;
        lp(j,0,N)
        {
            gridRota[i].emplace_back( mat[j][i] ) ;
            auxRota[i].emplace_back( *(new vector<pii>) ) ;
        }
    }

    solve(gridCerto, auxCerto ) ;
    solve( gridRota, auxRota  );

   /* lp(i,1,N-1)
    {
        lp(j,1,M-1)
        {
            printf("Na casinha %d %d -> " , i , j ) ;
            for(auto e : auxCerto[i][j] ) printf("%d %d, " , e.ff, e.ss ) ;
            printf("\n") ;
        }
    } */

    ll ans = 0LL ;

    lp(i,1,N-1)
        lp(j,1,M-1)
        {
            for(auto e : auxCerto[i][j] )
                for(auto ee : auxRota[j][i] )
                    ans += ( ee.ss >= e.ff && e.ss >= ee.ff ) ;
        }

    return ans ;

}

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