Submission #886535

#	Time	Username	Problem	Language	Result	Execution time	Memory
886535		ono_de206	Sandcastle 2 (JOI22_ho_t5)	C++14	24 / 100	5041 ms	102904 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 = 7010;
int a[mxn][mxn];
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;
}

bool add(int x) {
	set<int>::iterator it = s.lower_bound(x);
	int nx = -1, pr = -1;
	if(it != s.end()) {
		nx = *it;
	}
	if(it != s.begin()) {
		it--;
		pr = *it;
	}
	if(nx != -1) {
		cnt += get(x, nx);
	}
	if(pr != -1) {
		cnt += get(x, pr);
	}
	if(pr != -1 && nx != -1) {
		cnt -= get(pr, nx);
	}
	s.in(x);
	
	if(nx != -1 && pos[x].ff - pos[nx].ff > 1) return 0;
	if(pr != -1 && pos[x].ff - pos[pr].ff > 1) return 0;
	return 1;
}

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;
	if(n == 1) {
		solveH1(m);
		return 0;
	}
	vector<int> g;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(m <= n) cin >> a[i][j];
			else cin >> a[j][i];
		}
	}
	if(n < m) swap(n, m);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			g.pb(a[i][j]);
		}
	}
	sort(all(g));
	g.erase(unique(all(g)), g.end());
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			a[i][j] = lower_bound(all(g), a[i][j]) - g.begin() + 1;
			pos[a[i][j]] = make_pair(i, j);
		}
	}
	int ans = 0;
	for(int l = 1; l <= m; l++) {
		for(int r = l; r <= m; r++) {
			for(int i = 1; i <= n; i++) {
				s.clear();
				cnt = 0;
				for(int j = i; j <= n; j++) {
					bool is = 0;
					for(int k = l; k <= r; k++) {
						if(!add(a[j][k])) {
							is = 1;
							break;
						}
					}
					if(cnt == 0) ans++;
					if(is) break;
				}
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

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