Submission #1215337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215337		countless	Rectangles (IOI19_rect)	C++20	0 / 100	4 ms	8776 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = 5e3;

#define endl "\n"
#define sp <<" "<<
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define mp make_pair
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()

struct stuff {
	short coll, colr, rowl, rowr;

	stuff(short coll = -INF, short colr = INF, short rowl = -INF, short rowr = INF) : coll(coll), colr(colr), rowl(rowl), rowr(rowr) {;;}

	static stuff merge(const stuff &a, const stuff &b) {
		return stuff{min(a.coll, b.coll), max(a.colr, b.colr), min(a.rowl, b.rowl), max(a.rowr, b.rowr)};
	}

    static ll calc(const stuff &a) {
        // cerr << a.rowr - a.rowl - 1 sp a.colr - a.coll - 1 << endl;
        return ll(a.rowr - a.rowl - 1) * ll(a.colr - a.coll - 1);
    }
};

const stuff nothing = stuff{INF, -INF, INF, -INF};

short n, m;
int k;
const int dr[4] = {0, 0, -1, 1};
const int dc[4] = {-1, 1, 0, 0};

inline bool in(const short &x, const short &y) {
	return (0 < x and x < n-1 and 0 < y and y < m-1);
}

inline ll encode(const ll &x, const ll &y, const ll &xx, const ll &yy) {
	return ((x<<48)|(y<<32)|(xx<<16)|yy);
}

unordered_set<ll> vis;

ll count_rectangles(vector<vector<int>> a) {
	n = a.size(), m = a[0].size(), k = n * m;
	vector<vector<stuff>> base(n, vector<stuff>(m));
	vis.reserve(1 << 20);
	ll ans = 0;

    vector<pair<int, int>> ts(k);
	vector<int> st;

	for (short i = 0; i < n; i++) {
		st.clear();

		for (short j = 0; j < m; j++) {
			while (!st.empty() and a[i][st.back()] <= a[i][j]) {
				st.pop_back();
			}

			if (!st.empty()) {
				base[i][j].rowl = st.back();
			}

			st.push_back(j);
		}

		st.clear();

		for (short j = m-1; j >= 0; j--) {
			while (!st.empty() and a[i][st.back()] <= a[i][j]) {
				st.pop_back();
			}

			if (!st.empty()) {
				base[i][j].rowr = st.back();
			}

			st.push_back(j);

            int ind = i * m + j;
            ts[ind] = {a[i][j], ind};
		}
	}

	for (short i = 0; i < m ; i++) {
		st.clear();

		for (short j = 0; j < n; j++) {
			while (!st.empty() and a[st.back()][i] <= a[j][i]) {
				st.pop_back();
			}

			if (!st.empty()) {
				base[j][i].coll = st.back();
			}

			st.push_back(j);
		}

		st.clear();

		for (short j = n-1; j >= 0; j--) {
			while (!st.empty() and a[st.back()][i] <= a[j][i]) {
				st.pop_back();
			}

			if (!st.empty()) {
				base[j][i].colr = st.back();
			}

			st.push_back(j);
		}
	}

    sort(all(ts), [&](const auto &a, const auto &b) -> bool {
        return a.first < b.first;
    });

    vector<int> par(k), siz(k, 1);
    vector<bool> vs(k, false);
    iota(all(par), 0);

    auto find = [&](auto &&find, int u) -> int {
        if (u == par[u]) return u;
        return par[u] = find(find, par[u]);
    };

    auto unite = [&](int u, int v) -> void {
        u = find(find, u), v = find(find, v);
        if (u == v) return;
        // if (siz[u] < siz[v]) swap(u, v);
        par[v] = u;
        siz[u] += siz[v];

        int ur = u / m, uc = u % m;
        int vr = u / m, vc = u % m;
        base[ur][uc] = stuff::merge(base[ur][uc], base[vr][vc]);

        return;
    };

    auto ensure = [&](int u) -> bool {
        int ur = u / m, uc = u % m;
        // cerr << ur sp uc sp stuff::calc(base[ur][uc]) sp siz[u] << endl;
        return stuff::calc(base[ur][uc]) <= siz[u];
    };

    auto check = [&](int r, int c) -> bool {
        return 0 < r and r < n-1 and 0 < c and c < m-1;
    };

    for (int i = 0; i < k; i++) {
        int hash = ts[i].second;
        int r = hash / m, c = hash % m;
        if (!check(r, c)) continue;

        for (int j = 0; j < 4; j++) {
            int nr = r + dr[j], nc = c + dc[j];

            if (check(nr, nc) and vs[nr * m + nc]) {
                // cerr << "un" sp nr sp nc << endl;
                unite(hash, nr * m + nc);
            }
        }

        if (ensure(find(find, hash))) ans++;

        vs[hash] = true;
    }

	return ans;
}

// int main() {
// 	int n, m; cin >> n >> m;
// 	vector<vector<int>> a(n, vector<int>(m));
// 	REP(i, 0, n) {
// 		REP(j, 0, m) {
// 			cin >> a[i][j];
// 		}
// 	}

// 	cout << count_rectangles(a) << endl;
// }

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