Submission #886538

#	Time	Username	Problem	Language	Result	Execution time	Memory
886538		ono_de206	Sandcastle 2 (JOI22_ho_t5)	C++14	80 / 100	5007 ms	7256 KiB

Main

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

#define pb push_back
#define in insert
#define ff first
#define ss second
#define all(x) x.begin(),x.end()

//#define int long long

const int mxn = 50010;
int le[mxn], ri[mxn];
vector<vector<int>> g, a;
pair<int, int> pos[mxn];
set<int> s;
int cnt;

int get(int x, int y) {
	if(abs(pos[x].ff - pos[y].ff) + abs(pos[x].ss - pos[y].ss) > 1) return 1;
	return 0;
}

void solveH1(int n) {
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int ans = 1, tot = 1;
	for(int i = 1; i < n; i++) {
		if(a[i] > a[i - 1]) {
			tot++;
		} else {
			tot = 1;
		}
		ans += tot;
	}
	tot = 1;
	for(int i = n - 2; i >= 0; i--) {
		if(a[i] > a[i + 1]) {
			ans += tot;
			tot++;
		} else {
			tot = 1;
		}
	}
	cout << ans << '\n';
}

signed main() {
	// ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	int n, m;
	// cin >> n >> m;
	scanf("%d%d", &n, &m);
	if(n == 1) {
		solveH1(m);
		return 0;
	}
	a.resize(max(n, m) + 1, vector<int>(min(n, m) + 1));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(m <= n) scanf("%d", &a[i][j]); //cin >> a[i][j];
			else scanf("%d", &a[j][i]); //cin >> a[j][i];
		}
	}
	if(n < m) swap(n, m);
	g.resize(n + 1);
	vector<array<int, 3>> tmp(n * m);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			tmp[(i - 1) * m + j - 1] = {a[i][j], i, j};
		}
	}
	sort(all(tmp));
	for (int i = 0; i < tmp.size(); i++) {
		int &ii = tmp[i][1];
		int &jj = tmp[i][2];
		pos[i + 1] = {ii, jj};
		a[ii][jj] = i + 1;
	}
	for(int i = 1; i <= n * m; i++) {
		le[i] = ri[i] = -1;
	}
	// if(n <= 90 && n * m >= 6900) {
	// 	int ans = 0;
	// 	for(int i = 1; i <= n; i++) {
	// 		for(int j = 1; j <= m; j++) {
	// 			ans += (n - i + 1) * (m - j + 1);
	// 		}
	// 	}
	// 	cout << ans << '\n';
	// 	return 0;
	// }
	int ans = 0;
	int l = 1, r = 2;
	for(int l = 1; l <= m; l++) {
		for(int r = l; r <= m; r++) {
			for(int i = 1; i <= n; i++) {
				// g[i].pb(a[i][r]);
				// int rr = a[i][r];
				// int ll = r - l - 1;
				// while(ll >= 0 && rr < g[i][ll]) {
				// 	g[i][ll + 1] = g[i][ll];
				// 	ll--;
				// }
				// g[i][ll + 1] = rr;
				if(g[i].empty() || g[i].back() < a[i][r]) g[i].pb(a[i][r]);
				else g[i].insert(lower_bound(all(g[i]), a[i][r]), a[i][r]);
			}
			for(int i = 1; i <= n; i++) {
				cnt = 0;
				for(int j = i; j <= n; j++) {
					int pr = -1, ptr = 0;
					bool is = 0;
					for(int k = 0; k < r - l + 1; k++) {
						while(j != i && ptr < g[j - 1].size() && g[j][k] > g[j - 1][ptr]) {
							pr = g[j - 1][ptr];
							ptr++;
						}
						int nx = -1;
						if(j != i && ptr < g[j - 1].size()) nx = g[j - 1][ptr];
						
						if(nx != -1 && le[nx] != pr) is = 1;
						if(pr != -1 && ri[pr] != nx) is = 1;
						if(is) break;
						
						if(pr != -1) cnt += get(pr, g[j][k]);
						if(nx != -1) cnt += get(nx, g[j][k]);
						if(pr != -1 && nx != -1) cnt -= get(pr, nx);
						
						le[g[j][k]] = pr;
						ri[g[j][k]] = nx;
						if(nx != -1) le[nx] = g[j][k];
						if(pr != -1) ri[pr] = g[j][k];
						pr = g[j][k];
					}
					if(is) break;
					if(cnt == 0) ans++;
				}
			}
		}
		for(int i = 1; i <= n; i++) {
			g[i].clear();
		}
	}
	cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for (int i = 0; i < tmp.size(); i++) {
      |                  ~~^~~~~~~~~~~~
Main.cpp:116:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |       while(j != i && ptr < g[j - 1].size() && g[j][k] > g[j - 1][ptr]) {
      |                       ~~~~^~~~~~~~~~~~~~~~~
Main.cpp:121:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |       if(j != i && ptr < g[j - 1].size()) nx = g[j - 1][ptr];
      |                    ~~~~^~~~~~~~~~~~~~~~~
Main.cpp:95:6: warning: unused variable 'l' [-Wunused-variable]
   95 |  int l = 1, r = 2;
      |      ^
Main.cpp:95:13: warning: unused variable 'r' [-Wunused-variable]
   95 |  int l = 1, r = 2;
      |             ^
Main.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:62:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |    if(m <= n) scanf("%d", &a[i][j]); //cin >> a[i][j];
      |               ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |    else scanf("%d", &a[j][i]); //cin >> a[j][i];
      |         ~~~~~^~~~~~~~~~~~~~~~

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