Submission #1032402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032402		shmax	Rectangles (IOI19_rect)	C++14	37 / 100	5119 ms	882388 KiB

rect

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

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2")

using namespace std;
using i32 = int;
//#define int long long
#define len(x) (int)(x.size())
#define inf 1000'000'000'000'000'000LL
#define all(x) x.begin(), x.end()
#define low_bit(x) (x & (-x))

template<typename T>
using vec = vector<T>;

const int maxM = 701;

template<typename it>
struct SparseTable {

    using T = typename remove_reference<decltype(*declval<it>())>::type;
    vector<vector<T>> t;
    function<T(T, T)> f;
    vector<int> log;

    SparseTable() = default;

    SparseTable(it first, it last, function<T(T, T)> op) : t(1), f(op) {
        int n = distance(first, last);
        t.assign(32 - __builtin_clz(n), vector<T>(n));
        t[0].assign(first, last);
        //       calc log
        log.resize(n + 1);
        for (int i = 2; i <= n; i++)
            log[i] = log[i / 2] + 1;

        for (int i = 1; i < t.size(); i++)
            for (int j = 0; j < n - (1 << i) + 1; j++)
                t[i][j] = f(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
    }

    // returns f(a[l..r]) in O(1) time
    T get(int l, int r) {
        int h = log[r - l + 1];
        return f(t[h][l], t[h][r - (1 << h) + 1]);
    }
};

long long count_rectangles(std::vector<std::vector<i32>> a) {
    int n = len(a);
    int m = len(a[0]);
    long long ans = 0;
    vec<vec<bitset<maxM>>> b(n, vec<bitset<maxM>>(m));
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < m - 1; j++) {
            b[i][j].reset();
            int mx = a[i][j];
            for (int l = i; l < n - 1; l++) {
                mx = max(mx, a[l][j]);
                if (mx >= min(a[i - 1][j], a[l + 1][j])) continue;
                b[i][j][l] = true;
            }

        }
    }

    vec<vec<bitset<maxM>>> good(m, vec<bitset<maxM>>(m));

    vec<SparseTable<vec<int>::iterator>> maxVal;
    for (int i = 0; i < n; i++) {
        maxVal.emplace_back(all(a[i]), [](int a, int b) {
            return max(a, b);
        });
    }
    for (int l = 1; l < m - 1; l++) {
        for (int r = l; r < m - 1; r++) {
            for (int i = 0; i < n; i++) {
                good[l][r][i] = maxVal[i].get(l, r) < min(a[i][l - 1], a[i][r + 1]);
            }
        }
    }
    vec<vec<vec<short>>> lowest(m, vec<vec<short>>(m, vec<short>(n, 0)));
    for (int l = 1; l < m - 1; l++) {
        for (int r = l; r < m - 1; r++) {
            for (int i = n - 2; i >= 1; i--) {
                if (!good[l][r][i]) continue;
                lowest[l][r][i] = lowest[l][r][i + 1] + 1;
            }
        }
    }
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < m - 1; j++) {
            if (a[i][j] >= a[i - 1][j]) continue;
            if (a[i][j] >= a[i][j - 1]) continue;
            for (int k = j; k < m - 1; k++) {
                b[i][j] &= b[i][k];
                if(b[i][j].count() == 0) break;
                ans += (b[i][j] &
                        ((good[j][k] << (maxM - i - lowest[j][k][i])) >> (maxM - i - lowest[j][k][i]))).count();
            }
        }
    }

    return ans;
}

Compilation message (stderr)

rect.cpp: In instantiation of 'SparseTable<it>::SparseTable(it, it, std::function<typename std::remove_reference<decltype (* declval<it>())>::type(typename std::remove_reference<decltype (* declval<it>())>::type, typename std::remove_reference<decltype (* declval<it>())>::type)>) [with it = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; typename std::remove_reference<decltype (* declval<it>())>::type = int]':
/usr/include/c++/10/ext/new_allocator.h:150:4:   required from 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = SparseTable<__gnu_cxx::__normal_iterator<int*, std::vector<int> > >; _Args = {__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, count_rectangles(std::vector<std::vector<int> >)::<lambda(int, int)>}; _Tp = SparseTable<__gnu_cxx::__normal_iterator<int*, std::vector<int> > >]'
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_Tp1> >::construct(std::allocator_traits<std::allocator<_Tp1> >::allocator_type&, _Up*, _Args&& ...) [with _Up = SparseTable<__gnu_cxx::__normal_iterator<int*, std::vector<int> > >; _Args = {__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, count_rectangles(std::vector<std::vector<int> >)::<lambda(int, int)>}; _Tp = SparseTable<__gnu_cxx::__normal_iterator<int*, std::vector<int> > >; std::allocator_traits<std::allocator<_Tp1> >::allocator_type = std::allocator<SparseTable<__gnu_cxx::__normal_iterator<int*, std::vector<int> > > >]'
/usr/include/c++/10/bits/vector.tcc:115:30:   required from 'void std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, count_rectangles(std::vector<std::vector<int> >)::<lambda(int, int)>}; _Tp = SparseTable<__gnu_cxx::__normal_iterator<int*, std::vector<int> > >; _Alloc = std::allocator<SparseTable<__gnu_cxx::__normal_iterator<int*, std::vector<int> > > >]'
rect.cpp:76:10:   required from here
rect.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 1; i < t.size(); i++)
      |                         ~~^~~~~~~~~~

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