oj.uz

Submission #886535

# Submission time Handle Problem Language Result Execution time Memory
886535 2023-12-12T09:44:53 Z ono_de206 Sandcastle 2 (JOI22_ho_t5) C++14
24 / 100
 5000 ms 102904 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 4 ms 908 KB Output is correct
4 Correct 4 ms 1112 KB Output is correct
5 Correct 4 ms 988 KB Output is correct
6 Correct 4 ms 860 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 100 ms 41596 KB Output is correct
8 Correct 5 ms 41564 KB Output is correct
9 Correct 55 ms 2516 KB Output is correct
10 Correct 548 ms 2852 KB Output is correct
11 Correct 83 ms 21076 KB Output is correct
12 Correct 109 ms 21076 KB Output is correct
13 Correct 116 ms 2392 KB Output is correct
14 Correct 85 ms 2588 KB Output is correct
15 Correct 54 ms 2396 KB Output is correct
16 Correct 42 ms 2392 KB Output is correct

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 100 ms 41596 KB Output is correct
8 Correct 5 ms 41564 KB Output is correct
9 Correct 55 ms 2516 KB Output is correct
10 Correct 548 ms 2852 KB Output is correct
11 Correct 83 ms 21076 KB Output is correct
12 Correct 109 ms 21076 KB Output is correct
13 Correct 116 ms 2392 KB Output is correct
14 Correct 85 ms 2588 KB Output is correct
15 Correct 54 ms 2396 KB Output is correct
16 Correct 42 ms 2392 KB Output is correct
17 Correct 2448 ms 102904 KB Output is correct
18 Correct 581 ms 4736 KB Output is correct
19 Correct 34 ms 16984 KB Output is correct
20 Execution timed out 5041 ms 5276 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 100 ms 41596 KB Output is correct
8 Correct 5 ms 41564 KB Output is correct
9 Correct 55 ms 2516 KB Output is correct
10 Correct 548 ms 2852 KB Output is correct
11 Correct 83 ms 21076 KB Output is correct
12 Correct 109 ms 21076 KB Output is correct
13 Correct 116 ms 2392 KB Output is correct
14 Correct 85 ms 2588 KB Output is correct
15 Correct 54 ms 2396 KB Output is correct
16 Correct 42 ms 2392 KB Output is correct
17 Correct 2448 ms 102904 KB Output is correct
18 Correct 581 ms 4736 KB Output is correct
19 Correct 34 ms 16984 KB Output is correct
20 Execution timed out 5041 ms 5276 KB Time limit exceeded
21 Halted 0 ms 0 KB -