Submission #420898

#	Time	Username	Problem	Language	Result	Execution time	Memory
420898		yuto1115	Rectangles (IOI19_rect)	C++17	59 / 100	5061 ms	704944 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;

public:
    BIT(int n) : n(n), v(n + 1, 0) {}
    
    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 i) {
        assert(0 <= i and i < n);
        i++;
        ll res = 0;
        while (i >= 1) {
            res += v[i];
            i -= i & -i;
        }
        return res;
    }
};

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;
            }
        }
    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++;
                rq[{j, k}].eb(k - cnt + 1, i);
                pre = k;
            }
        }
    ll ans = 0;
    BIT cnt(n);
    for (auto &[p, v] : mp) {
        if (!rq.count(p)) continue;
        if (v.empty()) continue;
        vp &cur = rq[p];
//        for (auto[i, j] : cur) {
//            for (auto[ni, nj] : v) {
//                if (i <= ni and nj <= j) ans++;
//            }
//        }
        sort(all(cur));
        int it = cur.size() - 1;
        while (it >= 0 and cur[it].first > v.back().first) it--;
        rrep(i, v.size()) {
            cnt.add(v[i].second, 1);
            while (it >= 0 and (i == 0 or cur[it].first > v[i - 1].first)) {
                ans += cnt.sum(cur[it].second);
                it--;
            }
        }
        rep(i, v.size()) {
            cnt.add(v[i].second, -1);
        }
    }
    return ans;
}

• 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