oj.uz

Submission #280520

# Submission time Handle Problem Language Result Execution time Memory
280520 2020-08-22T21:28:55 Z CaroLinda Rectangles (IOI19_rect) C++14
72 / 100
 4104 ms 1048580 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()

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 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 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 0 ms 256 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 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 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 5 ms 1792 KB Output is correct
18 Correct 5 ms 1792 KB Output is correct
19 Correct 5 ms 1792 KB Output is correct
20 Correct 3 ms 1536 KB Output is correct
21 Correct 5 ms 1536 KB Output is correct
22 Correct 5 ms 1536 KB Output is correct
23 Correct 5 ms 1536 KB Output is correct
24 Correct 3 ms 896 KB Output is correct
25 Correct 0 ms 256 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 512 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 0 ms 256 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 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 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 5 ms 1792 KB Output is correct
18 Correct 5 ms 1792 KB Output is correct
19 Correct 5 ms 1792 KB Output is correct
20 Correct 3 ms 1536 KB Output is correct
21 Correct 5 ms 1536 KB Output is correct
22 Correct 5 ms 1536 KB Output is correct
23 Correct 5 ms 1536 KB Output is correct
24 Correct 3 ms 896 KB Output is correct
25 Correct 27 ms 8576 KB Output is correct
26 Correct 28 ms 8576 KB Output is correct
27 Correct 28 ms 8568 KB Output is correct
28 Correct 20 ms 6912 KB Output is correct
29 Correct 32 ms 7552 KB Output is correct
30 Correct 34 ms 7552 KB Output is correct
31 Correct 32 ms 7416 KB Output is correct
32 Correct 31 ms 7288 KB Output is correct
33 Correct 0 ms 256 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 512 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 0 ms 256 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 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 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 5 ms 1792 KB Output is correct
18 Correct 5 ms 1792 KB Output is correct
19 Correct 5 ms 1792 KB Output is correct
20 Correct 3 ms 1536 KB Output is correct
21 Correct 5 ms 1536 KB Output is correct
22 Correct 5 ms 1536 KB Output is correct
23 Correct 5 ms 1536 KB Output is correct
24 Correct 3 ms 896 KB Output is correct
25 Correct 27 ms 8576 KB Output is correct
26 Correct 28 ms 8576 KB Output is correct
27 Correct 28 ms 8568 KB Output is correct
28 Correct 20 ms 6912 KB Output is correct
29 Correct 32 ms 7552 KB Output is correct
30 Correct 34 ms 7552 KB Output is correct
31 Correct 32 ms 7416 KB Output is correct
32 Correct 31 ms 7288 KB Output is correct
33 Correct 249 ms 85112 KB Output is correct
34 Correct 230 ms 80120 KB Output is correct
35 Correct 253 ms 80156 KB Output is correct
36 Correct 250 ms 75256 KB Output is correct
37 Correct 415 ms 100472 KB Output is correct
38 Correct 406 ms 100216 KB Output is correct
39 Correct 414 ms 100344 KB Output is correct
40 Correct 384 ms 94300 KB Output is correct
41 Correct 200 ms 77304 KB Output is correct
42 Correct 246 ms 79736 KB Output is correct
43 Correct 458 ms 87800 KB Output is correct
44 Correct 466 ms 87928 KB Output is correct
45 Correct 227 ms 45508 KB Output is correct
46 Correct 228 ms 45304 KB Output is correct
47 Correct 435 ms 86264 KB Output is correct
48 Correct 445 ms 86264 KB Output is correct
49 Correct 0 ms 256 KB Output is correct
50 Correct 1 ms 384 KB Output is correct
51 Correct 1 ms 512 KB Output is correct
52 Correct 1 ms 384 KB Output is correct
53 Correct 0 ms 256 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1289 ms 432376 KB Output is correct
3 Correct 2990 ms 920788 KB Output is correct
4 Correct 2977 ms 925556 KB Output is correct
5 Correct 2960 ms 925480 KB Output is correct
6 Correct 755 ms 416760 KB Output is correct
7 Correct 1569 ms 776132 KB Output is correct
8 Correct 1659 ms 825928 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 256 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 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 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 5 ms 1792 KB Output is correct
18 Correct 5 ms 1792 KB Output is correct
19 Correct 5 ms 1792 KB Output is correct
20 Correct 3 ms 1536 KB Output is correct
21 Correct 5 ms 1536 KB Output is correct
22 Correct 5 ms 1536 KB Output is correct
23 Correct 5 ms 1536 KB Output is correct
24 Correct 3 ms 896 KB Output is correct
25 Correct 27 ms 8576 KB Output is correct
26 Correct 28 ms 8576 KB Output is correct
27 Correct 28 ms 8568 KB Output is correct
28 Correct 20 ms 6912 KB Output is correct
29 Correct 32 ms 7552 KB Output is correct
30 Correct 34 ms 7552 KB Output is correct
31 Correct 32 ms 7416 KB Output is correct
32 Correct 31 ms 7288 KB Output is correct
33 Correct 249 ms 85112 KB Output is correct
34 Correct 230 ms 80120 KB Output is correct
35 Correct 253 ms 80156 KB Output is correct
36 Correct 250 ms 75256 KB Output is correct
37 Correct 415 ms 100472 KB Output is correct
38 Correct 406 ms 100216 KB Output is correct
39 Correct 414 ms 100344 KB Output is correct
40 Correct 384 ms 94300 KB Output is correct
41 Correct 200 ms 77304 KB Output is correct
42 Correct 246 ms 79736 KB Output is correct
43 Correct 458 ms 87800 KB Output is correct
44 Correct 466 ms 87928 KB Output is correct
45 Correct 227 ms 45508 KB Output is correct
46 Correct 228 ms 45304 KB Output is correct
47 Correct 435 ms 86264 KB Output is correct
48 Correct 445 ms 86264 KB Output is correct
49 Correct 10 ms 1920 KB Output is correct
50 Correct 8 ms 1664 KB Output is correct
51 Correct 9 ms 1792 KB Output is correct
52 Correct 0 ms 256 KB Output is correct
53 Correct 10 ms 1920 KB Output is correct
54 Correct 10 ms 1920 KB Output is correct
55 Correct 10 ms 1920 KB Output is correct
56 Correct 10 ms 1920 KB Output is correct
57 Correct 10 ms 1920 KB Output is correct
58 Correct 0 ms 384 KB Output is correct
59 Correct 1 ms 384 KB Output is correct
60 Correct 0 ms 384 KB Output is correct
61 Correct 1289 ms 432376 KB Output is correct
62 Correct 2990 ms 920788 KB Output is correct
63 Correct 2977 ms 925556 KB Output is correct
64 Correct 2960 ms 925480 KB Output is correct
65 Correct 755 ms 416760 KB Output is correct
66 Correct 1569 ms 776132 KB Output is correct
67 Correct 1659 ms 825928 KB Output is correct
68 Correct 4104 ms 1031184 KB Output is correct
69 Correct 3685 ms 958840 KB Output is correct
70 Correct 4054 ms 959352 KB Output is correct
71 Correct 3898 ms 887032 KB Output is correct
72 Runtime error 3337 ms 1048580 KB Execution killed with signal 9
73 Halted 0 ms 0 KB -