Submission #1204488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204488		countless	Rectangles (IOI19_rect)	C++20	0 / 100	5059 ms	734328 KiB

rect

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

typedef long long ll;
typedef long double ld;

const ll MOD = 998244353;
const ll INF = 1e18;
const ld EPS = 1e-12;

#define endl "\n"
#define sp <<" "<<
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())

struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

template <typename Key, typename Value>
using hash_map = unordered_map<Key, Value, custom_hash>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// uniform_int_distribution<int>(a, b)(rng);
// shuffle(all(a), rng);

// d, u, r, l
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

ll count_rectangles(vector<vector<int>> a) {
	ll n = a.size(), m = a[0].size();
	ll ans = 0, curr;
	assert(n <= 30 and m <= 30);

	vector<pair<int, int>> b(n*m);
	REP(i, 0, n) {
		REP(j, 0, m) {
			b[i*m+j] = {a[i][j], i*m+j};
		}
	}

	sort(all(b));

	vector<vector<bool>> vis(n, vector<bool>(m, false)), good;
	good = vis;

	auto in = [&](int x, int y) -> bool {
		return (0 < x and x < n-1 and 0 < y and y < m-1);
	};

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

	auto bfs = [&](auto &&bfs, int xx, int yy) -> void {
		queue<int> q;
		q.push(xx*m+yy);
		vis[xx][yy] = true;

		while (!q.empty()) {
			int r = q.front(); q.pop();
			int x = r / m, y = r % m;
			
			vis[x][y] = true;

			bool ok = true;
			int nx[4], ny[4];
			REP(i, 0, 4) {
				nx[i] = x + dx[i], ny[i] = y + dy[i];
			}

			// d, u, r, l
			if (xx - x > 0) {
				nx[0] += xx - x;
			} else {
				nx[1] -= x - xx;
			}

			if (yy - y > 0) {
				ny[2] += yy - y;
			} else {
				ny[3] -= y - yy;
			}

			REP(i, 0, 4) {
				int nxx = nx[i], nyy = ny[i];
				if (check(nxx, nyy)) {
					if (!(a[nxx][nyy] > a[x][y] or good[nxx][nyy])) {
						ok = false;
						break;
					}
				}
			}

			if (ok) {
				good[x][y] = true;
				REP(i, 0, 4) {
					int nxx = nx[i], nyy = ny[i];
					if (in(nxx, nyy) and !vis[nxx][nyy]) {
						q.push(nxx*m+nyy);
					}
				}
				curr++;
			}
		}
	};

	REP(i, 0, n*m) {
		int x = b[i].second / m, y = b[i].second % m;
		if (in(x, y) and !vis[x][y]) {
			curr = 0;
			bfs(bfs, x, y);
			ans += curr;
		}
	}

	return ans;
}

• 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