Submission #1277286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277286		mdobric	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	460 ms	17980 KiB

Main

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

typedef long long ll;

const int maxn = 50005, lg = 16;
const ll inf = 1e9;
int h, w;
vector <vector <int> > a, b;
vector <vector <ll> > val[lg], pref[lg];
vector <int> v;
unordered_map <int, int> novi;
unordered_map <ll, int> bio;
ll ans;

ll find (int i, int j, int k, int mask){
	ll rez = pref[mask + 2][i][k];
	if (i > 0) rez -= pref[mask + 2][i - 1][k];
	rez += pref[mask + 1][j][k];
	rez -= pref[mask + 1][j - 1][k];
	rez += pref[mask + 3][j - 1][k] - pref[mask + 3][i][k];
	return rez;
}

void rotiraj (){
	for (int i = 0; i < w; i++){
		vector <int> red;
		for (int j = 0; j < h; j++){
			red.push_back(a[j][i]);
		}
		b.push_back(red);
		red.clear();
	}
	a.clear();
	for (int i = 0; i < w; i++){
		vector <int> red;
		for (int j = 0; j < h; j++){
			red.push_back(b[i][j]);
		}
		a.push_back(red);
		red.clear();
	}
	swap(h, w);
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> h >> w;
	for (int i = 0; i < h; i++){
		vector <int> red;
		for (int j = 0; j < w; j++){
			int x;
			cin >> x;
			red.push_back(x);
			v.push_back(x);
		}
		a.push_back(red);
		red.clear();
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) novi[v[i]] = i + 1;
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			a[i][j] = novi[a[i][j]];
		}
	}
	if (h > w) rotiraj();
	
	/*
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	*/

	for (int i = 0; i < h; i++){
		vector <ll> red;
		for (int j = 0; j < w; j++){
			red.push_back(a[i][j]);
		}
		for (int j = 0; j < 16; j++) val[j].push_back(red), pref[j].push_back(red);
	}
	for (int mask = 1; mask < 16; mask++){
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				val[0][i][j] = inf;
				if ((mask & 1) and i == 0);
				else if ((mask & 2) and i == h - 1);
				else if ((mask & 4) and j == 0);
				else if ((mask & 8) and j == w - 1);
				else{
					int maxi = 0, veci = 0;
					if ((mask & 1)){
						if (a[i - 1][j] > a[i][j]) veci = 1;
						else maxi = max(maxi, a[i - 1][j]);
					}
					if ((mask & 2)){
						if (a[i + 1][j] > a[i][j]) veci = 1;
						else maxi = max(maxi, a[i + 1][j]);
					}
					if ((mask & 4)){
						if (a[i][j - 1] > a[i][j]) veci = 1;
						else maxi = max(maxi, a[i][j - 1]);
					}
					if ((mask & 8)){
						if (a[i][j + 1] > a[i][j]) veci = 1;
						else maxi = max(maxi, a[i][j + 1]);
					}
					if (veci == 1) val[mask][i][j] = a[i][j] - maxi;
					else val[mask][i][j] = inf - maxi;
					
					//cout << i << " " << j << " " << mask << "   " << val[mask][i][j] << endl;
				}
				if (i == 0) pref[mask][i][j] = val[mask][i][j];
				else pref[mask][i][j] = pref[mask][i - 1][j] + val[mask][i][j];
			}
		}
	}
	
	for (int i = 0; i < h; i++){
		ans++;
		ll suma = val[4][i][0];
		ll srednji = val[12][i][0];
		bio[srednji - val[8][i][0]]++;
		//cout << i << " " << 0 << " " << ans << "\n";
		for (int j = 1; j < w; j++){
			suma -= val[4][i][j - 1];
			suma += val[12][i][j - 1];
			suma += val[4][i][j];
			srednji += val[12][i][j];
			ans += 1 + bio[suma - inf];
			bio[srednji - val[8][i][j]]++;
			//cout << i << " " << j << " " << ans << "\n";
			
		}
		bio.clear();
	}
	
	//cout << find(0, 1, 0, 8) << " " << find(0, 1, 1, 4) << endl;
	
	for (int i = 0; i < h; i++){
		for (int j = i + 1; j < h; j++){
			if (find(i, j, 0, 0) == inf) ans++;
			ll suma = find(i, j, 0, 4);
			ll srednji = find(i, j, 0, 12);
			bio[srednji - find(i, j, 0, 8)]++;
			//cout << i << " " << j << " " << 0 << " " << ans << endl;
			for (int k = 1; k < w; k++){
				if (find(i, j, k, 0) == inf) ans++;
				suma -= find(i, j, k - 1, 4);
				suma += find(i, j, k - 1, 12);
				suma += find(i, j, k, 4);
				srednji += find(i, j, k, 12);
				ans += bio[suma - inf];
				bio[srednji - find(i, j, k, 8)]++;
				//cout << i << " " << j << " " << k << " " << ans << endl;
			}
			bio.clear();
		}
	}
	cout << ans << "\n";

	return 0;
}

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