제출 #1264813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264813		kustov_vadim_533	Sandcastle 2 (JOI22_ho_t5)	C++20	10 / 100	5086 ms	3852 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;

#define len(v) (int)((v).size())


map<int, pair<int, int>> mp;

bool check(const pair<int, int> &p1, const pair<int, int> &p2){
	return (abs(p1.first - p2.first) + abs(p1.second - p2.second)) == 1;
}

bool check(int i){
	{
		auto it = mp.find(i);
		if (it != mp.begin() && !(check((--it)->second, mp[i]))){
			return false;
		}
	}
	{
		auto it = mp.find(i);
		++it;
		if (it != mp.end() && !(check(it->second, mp[i]))){
			return false;
		}
	}
	return true;
}

void solve() {
	int h, w;
	cin >> h >> w;
	vector<vector<int>> a(h, vector<int>(w));
	for (int i = 0; i < h; ++i){
		for (int j = 0; j < w; ++j){
			cin >> a[i][j];
		}
	}

	if (h > w){
		vector<vector<int>> b(w, vector<int>(h));
		for (int i = 0; i < h; ++i){
			for (int j = 0; j < w; ++j){
				b[j][i] = a[i][j];
			}
		}
		swap(h, w);
		a = b;
	}

	ll ans = 0;
	for (int li = 0; li < h; ++li){
		for (int ri = li; ri < h; ++ri){
			for (int lj = 0; lj < w; ++lj){
				int count = 0;
				mp.clear();

				for (int rj = lj; rj < w; ++rj){
					for (int i = li; i <= ri; ++i){
						mp[a[i][rj]] = {i, rj};

						int l = -1, r = -1;
						{
							auto it = mp.find(a[i][rj]);
							if (it != mp.begin()){
								--it;
								l = it->first;
							}
						}
						{
							auto it = mp.find(a[i][rj]);
							++it;
							if (it != mp.end()){
								r = it->first;
							}
						}

						mp.erase(a[i][rj]);
						if (l != -1){
							count -= check(l);
						}
						if (r != -1){
							count -= check(r);
						}

						mp[a[i][rj]] = {i, rj};
						if (l != -1){
							count += check(l);
						}
						if (r != -1){
							count += check(r);
						}
						count += check(a[i][rj]);
						count--;
					}

					ans += count == 0;
				}
			}
		}
	}
	cout << ans << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(60);

	int t = 1;
//	cin >> t;

	while (t--) {
		solve();
	}
}

• Subtask 1: 0 / 9
• Subtask 2: 10 / 10
• Subtask 3: 0 / 5
• Subtask 4: 0 / 56
• Subtask 5: 0 / 20