Submission #199939

#	Time	Username	Problem	Language	Result	Execution time	Memory
199939		tri	Rectangles (IOI19_rect)	C++14	72 / 100	4081 ms	255736 KiB

rect

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

using namespace __gnu_pbds;
typedef tree<
        int,
        null_type,
        less<int>,
        rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

const int MAXN = 2505;

int N, M;
ll ans = 0;

struct block {
    int l, r;
    int len;

    bool operator<(block o) {
        if (l != o.l) return l < o.l;
        if (r != o.r) return r < o.r;
        return len < o.len;
    }

    bool operator<(pi o) {
        if (l != o.f) return l < o.f;
        return r < o.s;
    }

    bool operator==(pi o) {
        return l == o.f && r == o.s;
    }
};

bool longestFirst(block a, block b) {
    if (a.len != b.len) return a.len > b.len;
    return a < b;
}

vector<pi> findRanges2(vi &a) {
    vector<pi> ranges;

    vi stk;

    for (int i = 0; i < a.size(); i++) {
        for (int j = stk.size() - 1; j >= 0; j--) {
            int pB = stk[j];
            if (pB + 1 < i) {
                ranges.pb({pB + 1, i - 1});
            }

            if (a[stk[j]] >= a[i]) {
                break;
            }
        }

        while (stk.size() && a[stk[stk.size() - 1]] <= a[i]) {
            stk.erase(--stk.end());
        }
        stk.pb(i);
    }

    sort(ranges.begin(), ranges.end());
    return ranges;
}

vector<pi> findRanges(vi &a) {

//
//    vector<pi> ranges;
//
//    set<int> active;
//
//    vector<pi> pts;
//    for (int i = 0; i < a.size(); i++) {
//        pts.pb({a[i], i});
//    }
//
//    sort(pts.begin(), pts.end());
//    reverse(pts.begin(), pts.end());
//
//    for (pi &x :pts) {
//        int cLoc = x.s;
//        auto it = active.upper_bound(cLoc);
//        if (it != active.end()) {
//            int above = *it;
//            if (cLoc + 1 < above) {
//                ranges.pb({cLoc + 1, above - 1});
//            }
//        }
//        if (it != active.begin()) {
//            it--;
//            int below = *it;
//
//            if (below + 1 < cLoc) {
//                ranges.pb({below + 1, cLoc - 1});
//            }
//        }
//        active.insert(cLoc);
//    }
//    sort(ranges.begin(), ranges.end());
    return findRanges2(a);
}



vector<pi> ranges[MAXN];

vector<block> rColumnQ[MAXN];

int mode = 0;

vector<block> matchPrev(vector<block> blocks, vector<pi> ranges, int cRow = -1) {

    vector<block> newBlocks;

//    sort(blocks.begin(), blocks.end());
//    sort(ranges.begin(), ranges.end());

    int nBI = 0;
    for (pi cR : ranges) {
        while (nBI < blocks.size() && blocks[nBI] < cR) {
            if (mode == 0) {
                block cBlock = blocks[nBI];
                // end of cBlock (no longer extended)
                rColumnQ[cBlock.r].pb({cRow - cBlock.len, cRow - 1, cBlock.r - cBlock.l + 1});
            }

            nBI++;
        }

        if (nBI < blocks.size() && blocks[nBI] == cR) {
            block cBlock = blocks[nBI];

            newBlocks.pb({cBlock.l, cBlock.r, cBlock.len + 1});

            nBI++;
        } else {
            newBlocks.pb({cR.f, cR.s, 1});
        }
    }

    while (nBI < blocks.size()) {
        if (mode == 0) {
            block cBlock = blocks[nBI];
            // end of cBlock (no longer extended)
            rColumnQ[cBlock.r].pb({cRow - cBlock.len, cRow - 1, cBlock.r - cBlock.l + 1});
        }

        nBI++;
    }

    return newBlocks;
}

vi getColumn(vector<vi> &a, int cI) {
    vi col;
    for (int i = 0; i < N; i++) {
        col.pb(a[i][cI]);
    }
    return col;
}

ll count_rectangles(vector<vi> a) {
    N = a.size();
    M = a[0].size();

//    ps("read");

    for (int cR = 1; cR < N; cR++) {
        ranges[cR] = findRanges(a[cR]);
//        if(cR% 100 == 0){
//            ps(cR);
//        }
    }

//    ps("step1");

    mode = 0;
    vector<block> cBlocks;
    for (int cR = 1; cR <= N; cR++) { // include N to flush all blocks at the end
        cBlocks = matchPrev(cBlocks, ranges[cR], cR);
    }

    cBlocks.clear();
    mode = 1;

    ordered_set osets[MAXN];

//    ps("here");

    for (int cC = 1; cC < M; cC++) {
        vi cCol = getColumn(a, cC);
        vector<pi> cRanges = findRanges(cCol);

        cBlocks = matchPrev(cBlocks, cRanges);

        sort(cBlocks.begin(), cBlocks.end(), longestFirst);
        sort(rColumnQ[cC].begin(), rColumnQ[cC].end(), longestFirst);

        int nBI = 0;
        for (block cQ : rColumnQ[cC]) {
            while (nBI < cBlocks.size() && cBlocks[nBI].len >= cQ.len) {
                block cBlock = cBlocks[nBI];
                osets[cBlock.r].insert(cBlock.l);
                nBI++;
            }

            for (int cR = cQ.l; cR <= cQ.r; cR++) {
                ans += osets[cR].size() - osets[cR].order_of_key(cQ.l);
            }
        }
        for (int cR = 0; cR <= N; cR++) {
            osets[cR].clear();
        }

        sort(cBlocks.begin(), cBlocks.end());
    }


    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'std::vector<std::pair<int, int> > findRanges2(vi&)':
rect.cpp:123:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); i++) {
                     ~~^~~~~~~~~~
rect.cpp: In function 'std::vector<block> matchPrev(std::vector<block>, std::vector<std::pair<int, int> >, int)':
rect.cpp:200:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (nBI < blocks.size() && blocks[nBI] < cR) {
                ~~~~^~~~~~~~~~~~~~~
rect.cpp:210:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (nBI < blocks.size() && blocks[nBI] == cR) {
             ~~~~^~~~~~~~~~~~~~~
rect.cpp:221:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (nBI < blocks.size()) {
            ~~~~^~~~~~~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:281:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (nBI < cBlocks.size() && cBlocks[nBI].len >= cQ.len) {
                    ~~~~^~~~~~~~~~~~~~~~

• 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: 0 / 28