Submission #282021

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

const int MAX = 2505 ;

using namespace std ;

int N , M ;
vector<int> esq, dir, getFreq, lastVisit , marca ;

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() ;
    marca.clear() ;
    marca.shrink_to_fit() ;

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

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

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

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

            int x = j+1 ;

            while( x != -1 && grid[i][x]<= grid[i][j] )
            {
                if( grid[i][x] == grid[i][j] ) marca[j] = true ;
                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( marca[j] == 0 && esq[j] != -1 && dir[j] != -1 )
                toPut[ i ][ esq[j]+1 ].emplace_back( mk(dir[j]-1 , i) ) ;

    }

   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 ;
int bit[MAX] ;

void upd(int pos, int idx) { for(int i = pos ; i < MAX ; i += (i&-i)) bit[i] += idx ; }
int qry(int pos)
{
    int tot = 0 ;
    for(int i = pos ; i > 0 ; i -= (i&-i)) tot += bit[i] ;
    return tot ;
}

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

            for(auto e : auxRota[j][i] ) upd( e.ff , 1 ) ;

            int ptr = 0 ;

            for(auto e : auxCerto[i][j] )
            {
                while( ptr < sz( auxRota[j][i] ) && auxRota[j][i][ptr].ss < e.ff )
                {

                    upd( auxRota[j][i][ptr].ff , -1 ) ;
                    ptr++ ;
                }

                ans += (ll)( qry(e.ss) ) ;

            }

            while( ptr < sz(auxRota[j][i]) )
            {
                upd(auxRota[j][i][ptr].ff, -1 ) ;
                ptr++ ;
            }


        }

    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