oj.uz

Submission #280496

# Submission time Handle Problem Language Result Execution time Memory
280496 2020-08-22T20:45:42 Z CaroLinda Rectangles (IOI19_rect) C++14
10 / 100
 1097 ms 446004 KB 
#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 ;

        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 ) toPut[ i ][ esq[j]+1 ].emplace_back( mk(dir[j]-1 , i) ) ;

    }

   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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Incorrect 1 ms 512 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Incorrect 1 ms 512 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Incorrect 1 ms 512 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Incorrect 1 ms 512 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1920 KB Output is correct
2 Correct 8 ms 1664 KB Output is correct
3 Correct 14 ms 1792 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 11 ms 1792 KB Output is correct
6 Correct 10 ms 1792 KB Output is correct
7 Correct 10 ms 1792 KB Output is correct
8 Correct 10 ms 1792 KB Output is correct
9 Correct 10 ms 1792 KB Output is correct
10 Correct 8 ms 1024 KB Output is correct
11 Correct 9 ms 1408 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1097 ms 446004 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Incorrect 1 ms 512 KB Output isn't correct
10 Halted 0 ms 0 KB -