oj.uz

Submission #1067949

# Submission time Handle Problem Language Result Execution time Memory
1067949 2024-08-21T05:57:39 Z Gromp15 Rectangles (IOI19_rect) C++17
10 / 100
 422 ms 1048576 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "rect.h"
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)

long long count_rectangles(std::vector<std::vector<int>> a) {
	int n = sz(a), m = sz(a[0]);
	vector ok(n, vector(n, vector<int>(m)));
	for (int i = 0; i < m; i++) {
		for (int j = 1; j < n-1; j++) {
			int mx = 0;
			for (int k = j; k < n-1; k++) {
				ckmax(mx, a[k][i]);
				ok[j][k][i] = (mx >= min(a[j-1][i], a[k+1][i])) + (i ? ok[j][k][i-1] : 0);
			}
		}
	}
	vector ok2(m, vector(m, vector<int>(n)));
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < m-1; j++) {
			int mx = 0;
			for (int k = j; k < m-1; k++) {
				ckmax(mx, a[i][k]);
				ok2[j][k][i] = (mx >= min(a[i][j-1], a[i][k+1])) + (i ? ok2[j][k][i-1] : 0);
			}
		}
	}
	long long ans = 0;
	for (int i = 1; i < n-1; i++) for (int j = i; j < n-1; j++) {
		for (int k = 1; k < m-1; k++) {
			int l = upper_bound(all(ok[i][j]), ok[i][j][k-1]) - ok[i][j].begin() - 1;
			if (l < k) continue;
			for (int t = k; t <= l; t++) {
				ans += !(ok[i][j][t] - ok[i][j][k-1]) && !(ok2[k][t][j] - ok2[k][t][i-1]);
			}
		}
	}
	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 343104 KB Output is correct
2 Correct 228 ms 247636 KB Output is correct
3 Correct 307 ms 343224 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 304 ms 343104 KB Output is correct
6 Correct 302 ms 343084 KB Output is correct
7 Correct 315 ms 343260 KB Output is correct
8 Correct 327 ms 343020 KB Output is correct
9 Correct 332 ms 343172 KB Output is correct
10 Correct 290 ms 343124 KB Output is correct
11 Correct 307 ms 342992 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 422 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -