Submission #280520

#	Time	Username	Problem	Language	Result	Execution time	Memory
280520		CaroLinda	Rectangles (IOI19_rect)	C++14	72 / 100	4104 ms	1048580 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()

using namespace std ;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>

int N , M ;
vector<int> esq, dir, getFreq, lastVisit ;
set<pii> s ;

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

    int tamLinha = sz( grid[0] ) ;

    esq.clear() ;
    esq.shrink_to_fit() ;
    dir.clear() ;
    dir.shrink_to_fit() ;
    getFreq.clear() ;
    getFreq.shrink_to_fit() ;
    lastVisit.clear() ;
    lastVisit.shrink_to_fit() ;

    lp(i,0,tamLinha + 5)
    {
        esq.eb(0) ;
        dir.eb(0) ;
        getFreq.eb(0) ;
        lastVisit.eb(0) ;
    }

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

        lp(j,0,tamLinha)
            esq[j] = dir[j] = -1 ;

        s.clear() ;

        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-1 ; 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-1 ; j++ )
    {
        lp(i,0,tamLinha+4) getFreq[i] = lastVisit[i] = -1 ;

        for(int i = sz(grid) - 2 ; i >= 1 ; i-- )
            for(auto &e : toPut[i][j] )
            {
                if( e.ff < 0 || e.ff > tamLinha - 1 ) continue ;

                if(  lastVisit[e.ff] != i+1 ) getFreq[e.ff] = i ;
                e.ss = getFreq[e.ff] ;
                lastVisit[e.ff] = i ;
            }
    }

}

vector< vector<int> > gridCerto , gridRota ;
vector< vector< vector<pii> > > auxCerto, auxRota ;
ordered_set o_set ;

ll count_rectangles( vector<vector<int> > mat )
{

    if( sz(mat) < 3 || sz(mat[0]) < 3 ) return 0LL ;

    N = sz(mat) ;
    M = sz( mat[0] ) ;

    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  );

    ll ans = 0LL ;

    lp(i,1,N-1)
        lp(j,1,M-1)
        {
            sort( all(auxCerto[i][j]) ) ;
            sort( all(auxRota[j][i]) , [&](pii i, pii j) { return i.ss < j.ss ; }) ;

            o_set.clear() ;

            lp(e,0, sz(auxRota[j][i]) ) o_set.insert( mk(auxRota[j][i][e].ff, e) ) ;

            int ptr = 0 ;

            for(auto e : auxCerto[i][j] )
            {
                while( ptr < sz( auxRota[j][i] ) && auxRota[j][i][ptr].ss < e.ff )
                {
                    auto it = o_set.find(mk(auxRota[j][i][ptr].ff, ptr) ) ;
                    if( it != o_set.end() ) o_set.erase( it ) ;
                    ptr++ ;
                }

                ans += (ll)( o_set.order_of_key( mk( e.ss+1, -1 ) ) ) ;

            }


        }

    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