제출 #143803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143803		dacin21	Rectangles (IOI19_rect)	C++14	100 / 100	4974 ms	905252 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


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, vector<vector<int> > *L, vector<vector<int> > *R){
    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, vector<vector<int> > *w){
            while(!s.empty() && s.top().first <= h){
                const int y2 = s.top().second;
                ret[abs(y-y2)].emplace_back(i, min(y, y2));
                if(w) (*w)[i][y2] = y;
                s.pop();
            }
            s.emplace(h, y);
        };
        for(int j=0;j<Y;++j){
            cand(j, v[i][j], R);
        }
        while(!s.empty()) s.pop();
        for(int j=Y-1;j>=0;--j){
            cand(j, v[i][j], L);
        }
    }
    /*for(auto &e:ret){
        sort(e.begin(), e.end());
        e.erase(unique(e.begin(), e.end()), e.end());
    }*/
    return ret;
}


ll count_rectangles(std::vector<std::vector<int> > a) {
    const int X = a.size(), Y = a[0].size();
    vector<vector<int> > right_larger(X, vector<int>(Y, -1)), left_larger(X, vector<int>(Y, -1));
    auto const row_ranges = precalc(a, &left_larger, &right_larger);
    auto const row_ds = build_ds(Y, row_ranges);
    auto const col_ranges = precalc(transposed(a), nullptr, nullptr);
    auto const col_ds = build_ds(X, col_ranges);
    //debug << named(row_ranges) << "\n";
    //debug << named(col_ranges) << "\n";
    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]);
                auto const tmp = right_larger[x+1][y-1];
                //if(dx == 2) debug << u << " " << named(tmp) << "\n";
                if(tmp!=-1){
                    const int y2 = tmp;
                    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 = left_larger[x+1][y+1];
                if(tmp!=-1){
                    const int y2 = tmp;
                    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: 13 / 13
• Subtask 7: 28 / 28