제출 #420872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420872		yuto1115	Rectangles (IOI19_rect)	C++17	28 / 100	5067 ms	561336 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;
    map<tuple<int, int, int, int>, int> ok;
    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);
                rep2(l, k - cnt + 1, k + 1) {
                    ok[{i, j, l, k}]++;
                }
                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++;
//                const vp &v = mp[{j, k}];
//                rq[{j, k}].eb(k - cnt + 1, i);
                rep2(l, k - cnt + 1, k + 1) {
                    ok[{l, k, i, j}]++;
                }
                pre = k;
            }
        }
    ll ans = 0;
    for (auto[_, cnt] : ok) if (cnt == 2) ans++;
    return ans;
//    BIT cnt(n);
//    for (auto &[p, v] : mp) {
//        if (!rq.count(p)) continue;
//        if (v.empty()) continue;
//        vp &cur = rq[p];
//        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(0, cur[it].second + 1);
//                it--;
//            }
//        }
//        rep(i, v.size()) {
//            cnt.add(v[i].second, -1);
//        }
//    }
//    return ans;
}

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