oj.uz

Submission #797745

# Submission time Handle Problem Language Result Execution time Memory
797745 2023-07-29T20:39:21 Z denniskim Sandcastle 2 (JOI22_ho_t5) C++17
100 / 100
 1351 ms 70672 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n, m;
vector< vector<ll> > a, chk, nu[110], tmp2;
vector<ll> tmp;
ll gap[50010], gap2[50010], gap3[50010];
ll on[50010], tlf[50010], trg[50010], lf[50010], md[50010], rg[50010];
ll cou[50010];
ll A[50010], B[50010];
ll all;
vector<ll> L, R, U, D;
ll dx[] = {-1, 1, 0, 0};
ll dy[] = {0, 0, -1, 1};
ll num[5][5][5][5];
ll ans;

void make_nu(void)
{
	for(ll x = 0 ; x < 81 ; x++)
	{
		for(ll i = 0 ; i <= n ; i++)
		{
			for(ll j = 0 ; j <= m ; j++)
				chk[i][j] = 0;
		}
		
		for(ll i = 1 ; i <= n ; i++)
		{
			for(ll j = 1 ; j <= m ; j++)
			{
				ll Ux = max(0LL, i - U[x]);
				ll Dx = min(n, i + D[x]);
				ll Lx = max(0LL, j - L[x]);
				ll Rx = min(m, j + R[x]);
				
				for(ll d = 0 ; d < 4 ; d++)
				{
					ll nx = i + dx[d];
					ll ny = j + dy[d];
					
					if(nx <= 0 || ny <= 0 || nx > n || ny > m)
						continue;
					
					if(!(Ux <= nx && nx <= Dx && Lx <= ny && ny <= Rx))
						continue;
					
					ll maxx = -INF;
					
					for(ll dd = 0 ; dd < 4 ; dd++)
					{
						ll nnx = nx + dx[dd];
						ll nny = ny + dy[dd];
						
						if(nnx <= 0 || nny <= 0 || nnx > n || nny > m)
							continue;
						
						if(!(Ux <= nnx && nnx <= Dx && Lx <= nny && nny <= Rx))
							continue;
						
						if(a[nx][ny] > a[nnx][nny])
							maxx = max(maxx, a[nnx][nny]);
					}
					
					if(maxx == a[i][j])
					{
						chk[i][j] = 1;
						break;
					}
				}
			}
		}
		
		for(ll i = 1 ; i <= n ; i++)
		{
			for(ll j = 1 ; j <= m ; j++)
				nu[x][i][j] = nu[x][i - 1][j] + nu[x][i][j - 1] - nu[x][i - 1][j - 1] + 1 - chk[i][j];
		}
	}
}

ll sum(ll X, ll x1, ll y1, ll x2, ll y2)
{
	return nu[X][x2][y2] - nu[X][x1 - 1][y2] - nu[X][x2][y1 - 1] + nu[X][x1 - 1][y1 - 1];
}

int main(void)
{
	fastio
	
	cin >> n >> m;
	
	ll fff = 0;
	
	if(n >= m)
		swap(n, m), fff = 1;
	
	for(ll i = 0 ; i <= m ; i++)
		tmp.push_back(0);
	
	for(ll i = 0 ; i <= n ; i++)
	{
		a.push_back(tmp);
		chk.push_back(tmp);
		
		for(ll j = 0 ; j < 81 ; j++)
			nu[j].push_back(tmp);
	}
	
	if(fff)
		swap(n, m);
	
	for(ll i = 1 ; i <= n ; i++)
	{
		for(ll j = 1 ; j <= m ; j++)
		{
			if(fff)
				cin >> a[j][i];
			else
				cin >> a[i][j];
		}
	}
	
	if(fff)
		swap(n, m);
	
	for(ll i = 0 ; i <= 2 ; i++)
	{
		for(ll j = 0 ; j <= 2 ; j++)
		{
			for(ll k = 0 ; k <= 2 ; k++)
			{
				for(ll l = 0 ; l <= 2 ; l++)
				{
					num[i][j][k][l] = (ll)L.size();
					L.push_back(i);
					R.push_back(j);
					U.push_back(k);
					D.push_back(l);
				}
			}
		}
	}
	
	make_nu();
	
	for(ll i = 1 ; i <= n ; i++)
	{
		for(ll j = i ; j <= n ; j++)
		{
			for(ll k = 0 ; k <= m ; k++)
				gap[k] = gap2[k] = gap3[k] = on[k] = tlf[k] = trg[k] = lf[k] = md[k] = rg[k] = 0;
			
			for(ll k = 1 ; k <= m ; k++)
			{
				if(j - i == 0)
					gap[k] += sum(num[2][2][0][0], i, k, i, k);
				else if(j - i == 1)
					gap[k] += sum(num[2][2][0][1], i, k, i, k) + sum(num[2][2][1][0], j, k, j, k);
				else if(j - i == 2)
					gap[k] += sum(num[2][2][0][2], i, k, i, k) + sum(num[2][2][1][1], i + 1, k, i + 1, k) + sum(num[2][2][2][0], j, k, j, k);
				else if(j - i == 3)
					gap[k] += sum(num[2][2][0][2], i, k, i, k) + sum(num[2][2][1][2], i + 1, k, i + 1, k) + sum(num[2][2][2][1], i + 2, k, i + 2, k) + sum(num[2][2][2][0], j, k, j, k);
				else
					gap[k] += sum(num[2][2][0][2], i, k, i, k) + sum(num[2][2][1][2], i + 1, k, i + 1, k) + sum(num[2][2][2][2], i + 2, k, j - 2, k) + sum(num[2][2][2][1], j - 1, k, j - 1, k) + sum(num[2][2][2][0], j, k, j, k);
			}
			
			for(ll k = 1 ; k <= m ; k++)
			{
				if(j - i == 0)
				{
					gap2[k] += sum(num[0][2][0][0], i, k, i, k);
					gap2[k] += sum(num[1][2][0][0], i, k + 1, i, k + 1);
					gap3[k] += sum(num[2][1][0][0], i, k, i, k);
					gap3[k] += sum(num[2][0][0][0], i, k + 1, i, k + 1);
					on[k] += sum(num[0][0][0][0], i, k, i, k);
					tlf[k] += sum(num[0][1][0][0], i, k, i, k);
					trg[k] += sum(num[1][0][0][0], i, k, i, k);
					lf[k] += sum(num[0][2][0][0], i, k, i, k);
					rg[k] += sum(num[2][0][0][0], i, k, i, k);
					md[k] += sum(num[1][1][0][0], i, k, i, k);
				}
				
				else if(j - i == 1)
				{
					gap2[k] += sum(num[0][2][0][1], i, k, i, k) + sum(num[0][2][1][0], j, k, j, k);
					gap2[k] += sum(num[1][2][0][1], i, k + 1, i, k + 1) + sum(num[1][2][1][0], j, k + 1, j, k + 1);
					gap3[k] += sum(num[2][1][0][1], i, k, i, k) + sum(num[2][1][1][0], j, k, j, k);
					gap3[k] += sum(num[2][0][0][1], i, k + 1, i, k + 1) + sum(num[2][0][1][0], j, k + 1, j, k + 1);
					on[k] += sum(num[0][0][0][1], i, k, i, k) + sum(num[0][0][1][0], j, k, j, k);
					tlf[k] += sum(num[0][1][0][1], i, k, i, k) + sum(num[0][1][1][0], j, k, j, k);
					trg[k] += sum(num[1][0][0][1], i, k, i, k) + sum(num[1][0][1][0], j, k, j, k);
					lf[k] += sum(num[0][2][0][1], i, k, i, k) + sum(num[0][2][1][0], j, k, j, k);
					rg[k] += sum(num[2][0][0][1], i, k, i, k) + sum(num[2][0][1][0], j, k, j, k);
					md[k] += sum(num[1][1][0][1], i, k, i, k) + sum(num[1][1][1][0], j, k, j, k);
				}
				
				else if(j - i == 2)
				{
					gap2[k] += sum(num[0][2][0][2], i, k, i, k) + sum(num[0][2][1][1], i + 1, k, i + 1, k) + sum(num[0][2][2][0], j, k, j, k);
					gap2[k] += sum(num[1][2][0][2], i, k + 1, i, k + 1) + sum(num[1][2][1][1], i + 1, k + 1, i + 1, k + 1) + sum(num[1][2][2][0], j, k + 1, j, k + 1);
					gap3[k] += sum(num[2][1][0][2], i, k, i, k) + sum(num[2][1][1][1], i + 1, k, i + 1, k) + sum(num[2][1][2][0], j, k, j, k);
					gap3[k] += sum(num[2][0][0][2], i, k + 1, i, k + 1) + sum(num[2][0][1][1], i + 1, k + 1, i + 1, k + 1) + sum(num[2][0][2][0], j, k + 1, j, k + 1);
					on[k] += sum(num[0][0][0][2], i, k, i, k) + sum(num[0][0][1][1], i + 1, k, i + 1, k) + sum(num[0][0][2][0], j, k, j, k);
					tlf[k] += sum(num[0][1][0][2], i, k, i, k) + sum(num[0][1][1][1], i + 1, k, i + 1, k) + sum(num[0][1][2][0], j, k, j, k);
					trg[k] += sum(num[1][0][0][2], i, k, i, k) + sum(num[1][0][1][1], i + 1, k, i + 1, k) + sum(num[1][0][2][0], j, k, j, k);
					lf[k] += sum(num[0][2][0][2], i, k, i, k) + sum(num[0][2][1][1], i + 1, k, i + 1, k) + sum(num[0][2][2][0], j, k, j, k);
					rg[k] += sum(num[2][0][0][2], i, k, i, k) + sum(num[2][0][1][1], i + 1, k, i + 1, k) + sum(num[2][0][2][0], j, k, j, k);
					md[k] += sum(num[1][1][0][2], i, k, i, k) + sum(num[1][1][1][1], i + 1, k, i + 1, k) + sum(num[1][1][2][0], j, k, j, k);
				}
				
				else if(j - i == 3)
				{
					gap2[k] += sum(num[0][2][0][2], i, k, i, k) + sum(num[0][2][1][2], i + 1, k, i + 1, k) + sum(num[0][2][2][1], i + 2, k, i + 2, k) + sum(num[0][2][2][0], j, k, j, k);
					gap2[k] += sum(num[1][2][0][2], i, k + 1, i, k + 1) + sum(num[1][2][1][2], i + 1, k + 1, i + 1, k + 1) + sum(num[1][2][2][1], i + 2, k + 1, i + 2, k + 1) + sum(num[1][2][2][0], j, k + 1, j, k + 1);
					gap3[k] += sum(num[2][1][0][2], i, k, i, k) + sum(num[2][1][1][2], i + 1, k, i + 1, k) + sum(num[2][1][2][1], i + 2, k, i + 2, k) + sum(num[2][1][2][0], j, k, j, k);
					gap3[k] += sum(num[2][0][0][2], i, k + 1, i, k + 1) + sum(num[2][0][1][2], i + 1, k + 1, i + 1, k + 1) + sum(num[2][0][2][1], i + 2, k + 1, i + 2, k + 1) + sum(num[2][0][2][0], j, k + 1, j, k + 1);
					on[k] += sum(num[0][0][0][2], i, k, i, k) + sum(num[0][0][1][2], i + 1, k, i + 1, k) + sum(num[0][0][2][1], i + 2, k, i + 2, k) + sum(num[0][0][2][0], j, k, j, k);
					tlf[k] += sum(num[0][1][0][2], i, k, i, k) + sum(num[0][1][1][2], i + 1, k, i + 1, k) + sum(num[0][1][2][1], i + 2, k, i + 2, k) + sum(num[0][1][2][0], j, k, j, k);
					trg[k] += sum(num[1][0][0][2], i, k, i, k) + sum(num[1][0][1][2], i + 1, k, i + 1, k) + sum(num[1][0][2][1], i + 2, k, i + 2, k) + sum(num[1][0][2][0], j, k, j, k);
					lf[k] += sum(num[0][2][0][2], i, k, i, k) + sum(num[0][2][1][2], i + 1, k, i + 1, k) + sum(num[0][2][2][1], i + 2, k, i + 2, k) + sum(num[0][2][2][0], j, k, j, k);
					rg[k] += sum(num[2][0][0][2], i, k, i, k) + sum(num[2][0][1][2], i + 1, k, i + 1, k) + sum(num[2][0][2][1], i + 2, k, i + 2, k) + sum(num[2][0][2][0], j, k, j, k);
					md[k] += sum(num[1][1][0][2], i, k, i, k) + sum(num[1][1][1][2], i + 1, k, i + 1, k) + sum(num[1][1][2][1], i + 2, k, i + 2, k) + sum(num[1][1][2][0], j, k, j, k);
				}
				
				else
				{
					gap2[k] += sum(num[0][2][0][2], i, k, i, k) + sum(num[0][2][1][2], i + 1, k, i + 1, k) + sum(num[0][2][2][2], i + 2, k, j - 2, k) + sum(num[0][2][2][1], j - 1, k, j - 1, k) + sum(num[0][2][2][0], j, k, j, k);
					gap2[k] += sum(num[1][2][0][2], i, k + 1, i, k + 1) + sum(num[1][2][1][2], i + 1, k + 1, i + 1, k + 1) + sum(num[1][2][2][2], i + 2, k + 1, j - 2, k + 1) + sum(num[1][2][2][1], j - 1, k + 1, j - 1, k + 1) + sum(num[1][2][2][0], j, k + 1, j, k + 1);
					gap3[k] += sum(num[2][1][0][2], i, k, i, k) + sum(num[2][1][1][2], i + 1, k, i + 1, k) + sum(num[2][1][2][2], i + 2, k, j - 2, k) + sum(num[2][1][2][1], j - 1, k, j - 1, k) + sum(num[2][1][2][0], j, k, j, k);
					gap3[k] += sum(num[2][0][0][2], i, k + 1, i, k + 1) + sum(num[2][0][1][2], i + 1, k + 1, i + 1, k + 1) + sum(num[2][0][2][2], i + 2, k + 1, j - 2, k + 1) + sum(num[2][0][2][1], j - 1, k + 1, j - 1, k + 1) + sum(num[2][0][2][0], j, k + 1, j, k + 1);
					on[k] += sum(num[0][0][0][2], i, k, i, k) + sum(num[0][0][1][2], i + 1, k, i + 1, k) + sum(num[0][0][2][2], i + 2, k, j - 2, k) + sum(num[0][0][2][1], j - 1, k, j - 1, k) + sum(num[0][0][2][0], j, k, j, k);
					tlf[k] += sum(num[0][1][0][2], i, k, i, k) + sum(num[0][1][1][2], i + 1, k, i + 1, k) + sum(num[0][1][2][2], i + 2, k, j - 2, k) + sum(num[0][1][2][1], j - 1, k, j - 1, k) + sum(num[0][1][2][0], j, k, j, k);
					trg[k] += sum(num[1][0][0][2], i, k, i, k) + sum(num[1][0][1][2], i + 1, k, i + 1, k) + sum(num[1][0][2][2], i + 2, k, j - 2, k) + sum(num[1][0][2][1], j - 1, k, j - 1, k) + sum(num[1][0][2][0], j, k, j, k);
					lf[k] += sum(num[0][2][0][2], i, k, i, k) + sum(num[0][2][1][2], i + 1, k, i + 1, k) + sum(num[0][2][2][2], i + 2, k, j - 2, k) + sum(num[0][2][2][1], j - 1, k, j - 1, k) + sum(num[0][2][2][0], j, k, j, k);
					rg[k] += sum(num[2][0][0][2], i, k, i, k) + sum(num[2][0][1][2], i + 1, k, i + 1, k) + sum(num[2][0][2][2], i + 2, k, j - 2, k) + sum(num[2][0][2][1], j - 1, k, j - 1, k) + sum(num[2][0][2][0], j, k, j, k);
					md[k] += sum(num[1][1][0][2], i, k, i, k) + sum(num[1][1][1][2], i + 1, k, i + 1, k) + sum(num[1][1][2][2], i + 2, k, j - 2, k) + sum(num[1][1][2][1], j - 1, k, j - 1, k) + sum(num[1][1][2][0], j, k, j, k);
				}
			}
			
			for(ll k = 1 ; k <= m ; k++)
				gap[k] += gap[k - 1];
					
			for(ll k = 1 ; k <= m ; k++)
			{
				if(k + 1 <= m)
					A[k] = gap[k + 1] - gap2[k];
				
				if(1 <= k - 2)
					B[k] = gap[k - 2] + gap3[k - 1];
			}
			
			for(ll k = 1 ; k <= m ; k++)
			{
				if(k >= 4)
					cou[A[k - 3]]++;
				
				if(k >= 4 && B[k] >= 1)
					ans += cou[B[k] - 1];
			}
			
			for(ll k = 1 ; k <= m ; k++)
				cou[A[k]] = 0;
			
			for(ll k = 1 ; k <= m ; k++)
			{
				if(k <= m)
				{
					if(on[k] == 1)
						ans++;
				}
				
				if(k + 1 <= m)
				{
					if(tlf[k] + trg[k + 1] == 1)
						ans++;
				}
				
				if(k + 2 <= m)
				{
					if(lf[k] + md[k + 1] + rg[k + 2] == 1)
						ans++;
				}
			}
		}
	}
	
	cout << ans;
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 109 ms 70348 KB Output is correct
3 Correct 121 ms 69200 KB Output is correct
4 Correct 114 ms 70284 KB Output is correct
5 Correct 124 ms 70288 KB Output is correct
6 Correct 136 ms 70528 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 5 ms 2440 KB Output is correct
8 Correct 4 ms 2372 KB Output is correct
9 Correct 12 ms 1544 KB Output is correct
10 Correct 8 ms 1492 KB Output is correct
11 Correct 4 ms 1876 KB Output is correct
12 Correct 5 ms 1876 KB Output is correct
13 Correct 9 ms 1532 KB Output is correct
14 Correct 7 ms 1236 KB Output is correct
15 Correct 14 ms 1460 KB Output is correct
16 Correct 12 ms 1488 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 5 ms 2440 KB Output is correct
8 Correct 4 ms 2372 KB Output is correct
9 Correct 12 ms 1544 KB Output is correct
10 Correct 8 ms 1492 KB Output is correct
11 Correct 4 ms 1876 KB Output is correct
12 Correct 5 ms 1876 KB Output is correct
13 Correct 9 ms 1532 KB Output is correct
14 Correct 7 ms 1236 KB Output is correct
15 Correct 14 ms 1460 KB Output is correct
16 Correct 12 ms 1488 KB Output is correct
17 Correct 16 ms 10148 KB Output is correct
18 Correct 64 ms 5380 KB Output is correct
19 Correct 41 ms 5404 KB Output is correct
20 Correct 67 ms 5332 KB Output is correct
21 Correct 71 ms 5420 KB Output is correct
22 Correct 66 ms 5412 KB Output is correct
23 Correct 65 ms 5204 KB Output is correct
24 Correct 53 ms 4832 KB Output is correct
25 Correct 71 ms 5564 KB Output is correct
26 Correct 74 ms 5460 KB Output is correct
27 Correct 85 ms 5560 KB Output is correct
28 Correct 77 ms 5408 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 5 ms 2440 KB Output is correct
8 Correct 4 ms 2372 KB Output is correct
9 Correct 12 ms 1544 KB Output is correct
10 Correct 8 ms 1492 KB Output is correct
11 Correct 4 ms 1876 KB Output is correct
12 Correct 5 ms 1876 KB Output is correct
13 Correct 9 ms 1532 KB Output is correct
14 Correct 7 ms 1236 KB Output is correct
15 Correct 14 ms 1460 KB Output is correct
16 Correct 12 ms 1488 KB Output is correct
17 Correct 16 ms 10148 KB Output is correct
18 Correct 64 ms 5380 KB Output is correct
19 Correct 41 ms 5404 KB Output is correct
20 Correct 67 ms 5332 KB Output is correct
21 Correct 71 ms 5420 KB Output is correct
22 Correct 66 ms 5412 KB Output is correct
23 Correct 65 ms 5204 KB Output is correct
24 Correct 53 ms 4832 KB Output is correct
25 Correct 71 ms 5564 KB Output is correct
26 Correct 74 ms 5460 KB Output is correct
27 Correct 85 ms 5560 KB Output is correct
28 Correct 77 ms 5408 KB Output is correct
29 Correct 128 ms 70672 KB Output is correct
30 Correct 472 ms 34472 KB Output is correct
31 Correct 1164 ms 34704 KB Output is correct
32 Correct 144 ms 52128 KB Output is correct
33 Correct 1112 ms 34508 KB Output is correct
34 Correct 1128 ms 34524 KB Output is correct
35 Correct 458 ms 23024 KB Output is correct
36 Correct 698 ms 33860 KB Output is correct
37 Correct 1128 ms 34340 KB Output is correct
38 Correct 1155 ms 34264 KB Output is correct
39 Correct 1129 ms 34344 KB Output is correct
40 Correct 1186 ms 34348 KB Output is correct
41 Correct 1142 ms 34352 KB Output is correct
42 Correct 1161 ms 34352 KB Output is correct
43 Correct 1351 ms 34280 KB Output is correct
44 Correct 1190 ms 34352 KB Output is correct