Submission #143802

#	Time	Username	Problem	Language	Result	Execution time	Memory
143802		dacin21	Rectangles (IOI19_rect)	C++14	59 / 100	3511 ms	1048580 KiB

rect

#include "rect.h"

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using fl = long double;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename S, typename T>
void xmin(S&a, T const&b){if(b<a) a=b;}
template<typename S, typename T>
void xmax(S&a, T const&b){if(b>a) a=b;}

template<bool enabled>
struct Debug{
    template<typename S, typename T = void> struct Tag_Printable : false_type {};
    template<typename S> struct Tag_Printable<S, decltype((void)(cerr << declval<S>()))> : true_type {};
    template<typename S, typename T = void> struct Tag_Iterable: false_type {};
    template<typename S> struct Tag_Iterable<S, decltype((void)(begin(declval<S>()), end(declval<S>())))> : true_type {};

    template<typename T, size_t N> struct Tuple_Printer{
        template<typename S>
        static S& print(S& stream, T const&t){
            return Tuple_Printer<T, N-1>::print(stream, t) << ", " << get<N>(t);
        }
    };
    template<typename T> struct Tuple_Printer<T, 0>{
        template<typename S>
        static S& print(S& stream, T const&t){
            return stream << get<0>(t);
        }
    };

    template<typename T, typename... Args>
    Debug& print(T const&x, true_type, Args...){
        #ifdef LOCAL_RUN
        if(enabled){
            cerr << boolalpha << x;
        }
        #endif // LOCAL_RUN
        return *this;
    }
    template<typename T>
    Debug& print(T const&x, false_type, true_type){
        *this << "[";
        bool first = true;
        for(auto &e:x){
            if(!first) *this << ", ";
            *this << e;
            first = false;
        }
        return *this << "]";
    }
    template<typename S, typename T>
    Debug& print(pair<S, T> const&x, false_type, false_type){
        return *this << "(" << x.first << ", " << x.second << ")";
    }
    template<typename... Args>
    Debug& print(tuple<Args...> const&t, false_type, false_type){
        return Tuple_Printer<decltype(t), sizeof...(Args)-1>::print(*this, t);
    }
    template<typename T>
    Debug& operator<<(T const&x){
        return print(x, Tag_Printable<T>{}, Tag_Iterable<T>{});
    }
};
 Debug<true> debug;
// Debug<false> debug; // disable debug printing
#define named(x) string(#x) << " : " <<  x


// Preprocesses in O(n log n) to allow you to query
// the next larger element to the left/right in O(log n)
template<typename Key, typename Value, typename value_comp = less<Value>>
class Cartesian_Ancestors{
public:
    // range maximum query in <n log n, 1>
    template<typename T = Value, typename comp = value_comp>
    class Sparsetable{
        int compind(int i, int j, int l, int sign)const{
            i = RMQ[lgn*i+l], j=RMQ[lgn*(j+sign*(1<<l))+l];
            return comp()(data[i], data[j])? j : i;
        }
        int minind(int l, int r)const{
            assert(l<r);
            return compind(l, r, lg2[r-l],-1);
        }
        void build(){
            lg2.resize(n+1);
            for(int i=2;i<=n;++i) lg2[i]=1+lg2[i/2];
            lgn = lg2.back()+1;
            RMQ.resize(n*lgn);
            for(int i=n-1;i>=0;--i){
                RMQ[lgn*i]=i;
                for(int j=0;j<lg2[n-i];++j) RMQ[lgn*i+j+1] = compind(i,i,j,1);
            }
        }
    public:
        Sparsetable() {}
        Sparsetable(vector<T> v): n(v.size()), data(move(v)) { build(); }
        /// max in [l, r)
        pair<int, T const&> operator()(int const&i, int const&j){
            int k = minind(i, j);
            return pair<int, T const&>(k, data[k]);
        }
        int n, lgn;
        vector<int> RMQ, lg2;
        vector<T> data;
    };
    struct Ret{
        int index;
        Key key;
        Value value;
        bool found;
        friend ostream& operator<<(ostream&o, Ret const&r){
            return o << "(" << r.index << ", " << r.key << ", " << r.value << ", " << r.found << ")";
        }
    };

    Cartesian_Ancestors(vector<Value> values) : n(values.size()), keys(n), data(move(values)), st(data){
        iota(keys.begin(), keys.end(), Key{});
    }
    Cartesian_Ancestors(vector<Key> keys_, vector<Value> values) : n(keys.size()), keys(move(keys_)), data(move(values)), st(data){
        assert(keys.size() == values.size());
        assert(is_sorted(keys.begin(), keys.end()));
    }
    Cartesian_Ancestors(vector<pair<Key, Value> > const&v) : n(v.size()), keys(n), data(n) {
        for(int i=0;i<n;++i){
            tie(keys[i], data[i]) = v[i];
        }
        assert(is_sorted(keys.begin(), keys.end()));
        st = Sparsetable<>(data);
    }

    template<bool allow_equal_key, bool allow_equal_value>
    Ret right_larger(Key const&key, Value const& value){
        auto it = allow_equal_key ? lower_bound(keys.begin(), keys.end(), key) : upper_bound(keys.begin(), keys.end(), key);
        int i = it - keys.begin();
        int l = i-1, r = n;
        while(l+1 < r){
            const int m = l + (r-l)/2;
            auto x = st(i, m+1).second;
            if(comp(x, value)){
                l = m;
            } else if(comp(value, x)){
                r = m;
            } else  {
                if(allow_equal_value){
                    r = m;
                } else {
                    l = m;
                }
            }
        }
        return ret_from_index(r);
    }
    template<bool allow_equal_key, bool allow_equal_value>
    Ret left_larger(Key const&key, Value const& value){
        auto it = allow_equal_key ? upper_bound(keys.begin(), keys.end(), key) : lower_bound(keys.begin(), keys.end(), key);
        int i = it - keys.begin();
        int l = -1, r = i;
        while(l+1 < r){
            const int m = l + (r-l)/2;
            auto x = st(m,i).second;
            if(comp(x, value)){
                r = m;
            } else if(comp(value, x)){
                l = m;
            } else  {
                if(allow_equal_value){
                    l = m;
                } else {
                    r = m;
                }
            }
        }
        return ret_from_index(l);
    }
private:
    Ret ret_from_index(int index){
        if(index == -1 || index == n) return Ret{index, Key{}, Value{}, false};
        return Ret{index, keys[index], data[index], true};
    }
    int n;
    vector<Key> keys;
    vector<Value> data;
    Sparsetable<> st;
    value_comp comp;
};

vector<vector<int> > transposed(vector<vector<int> > const&v){
    const int n = v.size(), m = v.empty() ? 0 : v[0].size();
    vector<vector<int> > ret(m, vector<int>(n));
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            ret[j][i] = v[i][j];
        }
    }
    return ret;
}


struct Range_And{
    Range_And(){}
    Range_And(int Y_, vector<pair<int, int> > const&v) : Y(Y_), data(Y){
        for(auto const&e:v){
            data[e.second].emplace_back(e.first);
        }
        for(auto &e:data){
            sort(e.begin(), e.end());
            e.erase(unique(e.begin(), e.end()), e.end());
        }
    }
    // all points present in {x} x [y1, y2)
    bool all(int x, int y1, int y2) const {
        const int dy = y2-y1;
        auto it = lower_bound(data[x].begin(), data[x].end(), y1);
        return data[x].end() - it >= dy && it[dy-1]<y2;
        //auto it2 = lower_bound(data[x].begin(), data[x].end(), y2);
        //return it2-it == y2-y1;
    }
    int Y;
    vector<vector<int> > data;
};

vector<Range_And> build_ds(int X, vector<vector<pair<int, int> > > const&v){
    vector<Range_And> ret;
    for(auto const&e:v){
        ret.emplace_back(X, e);
    }
    return ret;
}

// compute good ranges
vector<vector<pair<int, int> > > precalc(vector<vector<int> > const&v){
    const int X = v.size(), Y = v[0].size();
    vector<vector<pair<int, int> > > ret(Y);
    for(int i=0;i<X;++i){
        stack<pair<int, int> > s; // value, y
        auto cand = [&](int y, int h){
            while(!s.empty() && s.top().first <= h){
                const int y2 = s.top().second;
                ret[abs(y-y2)].emplace_back(i, min(y, y2));
                s.pop();
            }
            s.emplace(h, y);
        };
        for(int j=0;j<Y;++j){
            cand(j, v[i][j]);
        }
        while(!s.empty()) s.pop();
        for(int j=Y-1;j>=0;--j){
            cand(j, v[i][j]);
        }
    }
    /*for(auto &e:ret){
        sort(e.begin(), e.end());
        e.erase(unique(e.begin(), e.end()), e.end());
    }*/
    return ret;
}

using Cart = Cartesian_Ancestors<int, int>;

ll count_rectangles(std::vector<std::vector<int> > a) {
    const int X = a.size(), Y = a[0].size();
    auto const row_ranges = precalc(a);
    auto const row_ds = build_ds(Y, row_ranges);
    auto const col_ranges = precalc(transposed(a));
    auto const col_ds = build_ds(X, col_ranges);
    //debug << named(row_ranges) << "\n";
    //debug << named(col_ranges) << "\n";
    vector<Cart> row_cart;
    for(auto const&e:a){
        row_cart.emplace_back(e);
    }

    vector<tuple<int, int, int, int> > ret;
    auto add_rec = [&](int x1, int x2, int y1, int y2){
        ret.emplace_back(x1, x2, y1, y2);
        //debug << "Rec: " << ret.back() << "\n";
    };

    for(int dx=2;dx<X;++dx){
        for(auto const&u:col_ranges[dx]){
            const int y = u.first, x = u.second;
            // top left corner
            if(y!=0){
                auto const tmp = row_cart[x+1].right_larger<false, true>(y-1, a[x+1][y-1]);
                //if(dx == 2) debug << u << " " << named(tmp) << "\n";
                if(tmp.found){
                    const int y2 = tmp.index;
                    const int dy = y2-y+1;
                    if(dy != 1){
                        if(col_ds[dx].all(x, y, y2) && row_ds[dy].all(y-1, x+1, x+dx)){
                            add_rec(x+1, x+dx-1, y, y2-1);
                        }
                    }
                }
            }

            // top right corner
            if(y+1 != Y){
                auto const tmp = row_cart[x+1].left_larger<false, true>(y+1, a[x+1][y+1]);
                if(tmp.found){
                    const int y2 = tmp.index;
                    const int dy = y-y2+1;
                    if(dy != 1){
                        if(col_ds[dx].all(x, y2+1, y+1) && row_ds[dy].all(y2, x+1, x+dx)){
                            add_rec(x+1, x+dx-1, y2+1, y);
                        }
                    }
                }
            }
        }
    }




    sort(ret.begin(), ret.end());
    ret.erase(unique(ret.begin(), ret.end()), ret.end());
    return ret.size();
}

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