Submission #420762

#	Time	Username	Problem	Language	Result	Execution time	Memory
420762		yuto1115	Rectangles (IOI19_rect)	C++17	10 / 100	5086 ms	639388 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int inf = 1001001001;
const ll linf = 1001001001001001001;

class BIT {
    int n;
    vl v;
    
    ll sum(int i) {
        i++;
        ll res = 0;
        while (i >= 1) {
            res += v[i];
            i -= i & -i;
        }
        return res;
    }

public:
    BIT(int n) : n(n), v(n + 1) {}
    
    void add(int i, int x) {
        assert(0 <= i and i < n);
        i++;
        while (i <= n) {
            v[i] += x;
            i += i & -i;
        }
    }
    
    ll sum(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        return sum(r - 1) - sum(l - 1);
    }
};

ll count_rectangles(vvi a) {
    int n = a.size(), m = a[0].size();
    if (n < 3 or m < 3) return 0;
    vvvi col_fix(m, vvi(m));
    rep2(i, 1, n - 1) {
        stack<int> st;
        rep(j, m) {
            while (!st.empty() and a[i][st.top()] < a[i][j]) {
                if (st.top() < j - 1) col_fix[st.top() + 1][j - 1].pb(i);
                st.pop();
            }
            if (!st.empty()) {
                if (st.top() < j - 1) col_fix[st.top() + 1][j - 1].pb(i);
                if (a[i][st.top()] == a[i][j]) st.pop();
            }
            st.push(j);
        }
    }
    vvvi row_fix(n, vvi(n));
    rep2(i, 1, m - 1) {
        stack<int> st;
        rep(j, n) {
            while (!st.empty() and a[st.top()][i] < a[j][i]) {
                if (st.top() < j - 1) row_fix[st.top() + 1][j - 1].pb(i);
                st.pop();
            }
            if (!st.empty()) {
                if (st.top() < j - 1) row_fix[st.top() + 1][j - 1].pb(i);
                if (a[st.top()][i] == a[j][i]) st.pop();
            }
            st.push(j);
        }
    }
    // {bottom, right} -> {left, top}
    map<P, vp> mp;
    rep(i, m) rep(j, m) {
            int pre = -1, cnt = 0;
            for (int k : col_fix[i][j]) {
                if (pre + 1 < k) cnt = 0;
                cnt++;
                mp[{k, j}].eb(i, k - cnt + 1);
                pre = k;
            }
        }
    for (auto &[p, v] : mp) sort(all(v));
    map<P, vp> rq;
    rep(i, n) rep(j, n) {
            int pre = -1, cnt = 0;
            for (int k : row_fix[i][j]) {
                if (pre + 1 < k) cnt = 0;
                cnt++;
                const vp &v = mp[{j, k}];
                int it = lower_bound(all(v), P{k - cnt + 1, -1}) - v.begin();
                if (it < v.size()) {
                    rq[{j, k}].eb(it, i);
                }
                pre = k;
            }
        }
    ll ans = 0;
    BIT bt(n);
    for (auto &[p, v] : mp) {
        if (!rq.count(p)) continue;
        vp &cur = rq[p];
        int it = cur.size() - 1;
        rrep(i, v.size()) {
            bt.add(v[i].second, 1);
            while (it >= 0 and cur[it].first == i) {
                ans += bt.sum(0, cur[it].second + 1);
                it--;
            }
        }
        rep(i, v.size()) {
            bt.add(v[i].second, -1);
        }
    }
    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(vvi)':
rect.cpp:130:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |                 if (it < v.size()) {
      |                     ~~~^~~~~~~~~~

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