oj.uz

Submission #579456

# Submission time Handle Problem Language Result Execution time Memory
579456 2022-06-19T07:52:53 Z djs100201 Rectangles (IOI19_rect) C++17
100 / 100
 4163 ms 576992 KB 
#include "rect.h"
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using ll = long long;
using namespace std;
const int n_ = 2501;
using P = pair<int, int>;
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, base, ans, q;
short R[n_][n_], U[n_][n_], D[n_][n_], L[n_][n_];
vector<short>row[n_][n_];
vector<int>idx[n_][n_];
short tree_[n_];
short f(short l, short r) {
	r++;
	short ret = 0;
	for (; l; l -= (l & -l))ret -= tree_[l];
	for (; r; r -= (r & -r))ret += tree_[r];
	return ret;
}
void update(short i, short val) {
	i++;
	for (; i <= max(n, m); i += i & -i)tree_[i] += val;
}
int get(short x, short y) {
	return x * n_+ y;
}
long long count_rectangles(std::vector<std::vector<int> > arr) {
	ll ret = 0;
	n = arr.size();
	m = arr[0].size();
	for (int i = 0; i < n; i++) {
		stack<P>A, B;
		A.push({ arr[i][0],0 });
		B.push({ arr[i][m - 1],m - 1 });
		for (int j = 1; j < m; j++) {
			while (A.size() && A.top().first <= arr[i][j])A.pop();
			if (A.empty())L[i][j] = -1;
			else L[i][j] = A.top().second;
			A.push({ arr[i][j],j });
			while (B.size() && B.top().first <= arr[i][m - 1 - j])B.pop();
			if (B.empty())R[i][m - 1 - j] = -1;
			else R[i][m - 1 - j] = B.top().second;
			B.push({ arr[i][m - 1 - j],m - 1 - j });
		}
	}
	for (int i = 0; i < m; i++) {
		stack<P>A, B;
		A.push({ arr[0][i],0 });
		B.push({ arr[n - 1][i],n - 1 });
		for (int j = 1; j < n; j++) {
			while (A.size() && A.top().first <= arr[j][i])A.pop();
			if (A.empty())U[j][i] = -1;
			else U[j][i] = A.top().second;
			A.push({ arr[j][i],j });
			while (B.size() && B.top().first <= arr[n - 1 - j][i])B.pop();
			if (B.empty())D[n - 1 - j][i] = -1;
			else D[n - 1 - j][i] = B.top().second;
			B.push({ arr[n - 1 - j][i],n - 1 - j });
		}
	}
	vector<P>query;
	for (int j = 1; j + 1 < m; j++)
		for (int i = 1; i + 1 < n; i++) {
			if (D[i][j] == -1 || U[i][j] == -1)continue;
			if (row[U[i][j]][D[i][j]].size() && row[U[i][j]][D[i][j]].back() == j)continue;
			row[U[i][j]][D[i][j]].push_back(j);
			if (L[i][j] != -1 && R[i][j] != -1) {
				query.push_back({get(L[i][j],R[i][j]),get(U[i][j],D[i][j]) });
			}
		}
	sort(all(query));
	query.erase(unique(query.begin(), query.end()), query.end());
	int cnt = 0;
	for (auto nxt : query) {
		idx[nxt.second/n_][nxt.second%n_].push_back(cnt);
		cnt++;
	}
	assert(cnt <= n * m);
	vector<int>now(cnt + 1);
	for (int i = 0; i < n; i++)
		for (int j = i + 2; j < n; j++) {
			for (auto nxt : row[i][j])update(nxt, 1);
			for (auto nxt : idx[i][j]) {
				ll l = query[nxt].first/n_, r = query[nxt].first%n_;
				int len = f(l + 1, r - 1);
				if (len == r - l - 1)now[nxt]++;
			}
			for (auto nxt : row[i][j])update(nxt, -1);
			row[i][j].clear();
			idx[i][j].clear();
		}
	cnt = 0;
	for (auto nxt : query) {
		if (now[cnt] == 0) {
			cnt++;
			continue;
		}
		idx[nxt.first / n_][nxt.first % n_].push_back(cnt);
		cnt++;
	}
	for (int i = 1; i + 1 < n; i++)
		for (int j = 1; j + 1 < m; j++) {
			if (L[i][j] == -1 || R[i][j] == -1)continue;
			if (row[L[i][j]][R[i][j]].size() && row[L[i][j]][R[i][j]].back() == i)continue;
			row[L[i][j]][R[i][j]].push_back(i);
		}
	for (int i = 0; i < m; i++)
		for (int j = i + 2; j < m; j++) {
			for (auto nxt : row[i][j])update(nxt, 1);
			for (auto nxt : idx[i][j]) {
				ll l = query[nxt].second/n_, r = query[nxt].second%n_;
				int len = f(l + 1, r - 1);
				if (len == r - l - 1)ret++;
			}
			for (auto nxt : row[i][j])update(nxt, -1);
		}
	return ret;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 294184 KB Output is correct
2 Correct 133 ms 294544 KB Output is correct
3 Correct 133 ms 294500 KB Output is correct
4 Correct 137 ms 294608 KB Output is correct
5 Correct 135 ms 294584 KB Output is correct
6 Correct 134 ms 294612 KB Output is correct
7 Correct 134 ms 294512 KB Output is correct
8 Correct 131 ms 294188 KB Output is correct
9 Correct 136 ms 294492 KB Output is correct
10 Correct 132 ms 294552 KB Output is correct
11 Correct 136 ms 294504 KB Output is correct
12 Correct 133 ms 294596 KB Output is correct
13 Correct 133 ms 294056 KB Output is correct
14 Correct 140 ms 294132 KB Output is correct
15 Correct 137 ms 294144 KB Output is correct
16 Correct 139 ms 294020 KB Output is correct
17 Correct 135 ms 294032 KB Output is correct
18 Correct 141 ms 294016 KB Output is correct
19 Correct 133 ms 294472 KB Output is correct
20 Correct 132 ms 294476 KB Output is correct
21 Correct 135 ms 294220 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 294184 KB Output is correct
2 Correct 133 ms 294544 KB Output is correct
3 Correct 133 ms 294500 KB Output is correct
4 Correct 137 ms 294608 KB Output is correct
5 Correct 135 ms 294584 KB Output is correct
6 Correct 134 ms 294612 KB Output is correct
7 Correct 134 ms 294512 KB Output is correct
8 Correct 131 ms 294188 KB Output is correct
9 Correct 136 ms 294492 KB Output is correct
10 Correct 132 ms 294552 KB Output is correct
11 Correct 136 ms 294504 KB Output is correct
12 Correct 133 ms 294596 KB Output is correct
13 Correct 133 ms 294056 KB Output is correct
14 Correct 140 ms 294132 KB Output is correct
15 Correct 137 ms 294144 KB Output is correct
16 Correct 139 ms 294020 KB Output is correct
17 Correct 135 ms 294032 KB Output is correct
18 Correct 141 ms 294016 KB Output is correct
19 Correct 133 ms 294472 KB Output is correct
20 Correct 132 ms 294476 KB Output is correct
21 Correct 135 ms 294220 KB Output is correct
22 Correct 134 ms 295560 KB Output is correct
23 Correct 142 ms 295524 KB Output is correct
24 Correct 134 ms 295508 KB Output is correct
25 Correct 137 ms 295476 KB Output is correct
26 Correct 152 ms 295532 KB Output is correct
27 Correct 146 ms 295584 KB Output is correct
28 Correct 149 ms 295536 KB Output is correct
29 Correct 138 ms 295392 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 294184 KB Output is correct
2 Correct 133 ms 294544 KB Output is correct
3 Correct 133 ms 294500 KB Output is correct
4 Correct 137 ms 294608 KB Output is correct
5 Correct 135 ms 294584 KB Output is correct
6 Correct 134 ms 294612 KB Output is correct
7 Correct 134 ms 294512 KB Output is correct
8 Correct 131 ms 294188 KB Output is correct
9 Correct 136 ms 294492 KB Output is correct
10 Correct 132 ms 294552 KB Output is correct
11 Correct 136 ms 294504 KB Output is correct
12 Correct 133 ms 294596 KB Output is correct
13 Correct 133 ms 294056 KB Output is correct
14 Correct 140 ms 294132 KB Output is correct
15 Correct 137 ms 294144 KB Output is correct
16 Correct 139 ms 294020 KB Output is correct
17 Correct 134 ms 295560 KB Output is correct
18 Correct 142 ms 295524 KB Output is correct
19 Correct 134 ms 295508 KB Output is correct
20 Correct 137 ms 295476 KB Output is correct
21 Correct 152 ms 295532 KB Output is correct
22 Correct 146 ms 295584 KB Output is correct
23 Correct 149 ms 295536 KB Output is correct
24 Correct 138 ms 295392 KB Output is correct
25 Correct 135 ms 294032 KB Output is correct
26 Correct 141 ms 294016 KB Output is correct
27 Correct 133 ms 294472 KB Output is correct
28 Correct 132 ms 294476 KB Output is correct
29 Correct 135 ms 294220 KB Output is correct
30 Correct 152 ms 298616 KB Output is correct
31 Correct 164 ms 298656 KB Output is correct
32 Correct 155 ms 298704 KB Output is correct
33 Correct 166 ms 298180 KB Output is correct
34 Correct 150 ms 299028 KB Output is correct
35 Correct 151 ms 298876 KB Output is correct
36 Correct 148 ms 298760 KB Output is correct
37 Correct 159 ms 298796 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 294184 KB Output is correct
2 Correct 133 ms 294544 KB Output is correct
3 Correct 133 ms 294500 KB Output is correct
4 Correct 137 ms 294608 KB Output is correct
5 Correct 135 ms 294584 KB Output is correct
6 Correct 134 ms 294612 KB Output is correct
7 Correct 134 ms 294512 KB Output is correct
8 Correct 131 ms 294188 KB Output is correct
9 Correct 136 ms 294492 KB Output is correct
10 Correct 132 ms 294552 KB Output is correct
11 Correct 136 ms 294504 KB Output is correct
12 Correct 133 ms 294596 KB Output is correct
13 Correct 133 ms 294056 KB Output is correct
14 Correct 140 ms 294132 KB Output is correct
15 Correct 137 ms 294144 KB Output is correct
16 Correct 139 ms 294020 KB Output is correct
17 Correct 134 ms 295560 KB Output is correct
18 Correct 142 ms 295524 KB Output is correct
19 Correct 134 ms 295508 KB Output is correct
20 Correct 137 ms 295476 KB Output is correct
21 Correct 152 ms 295532 KB Output is correct
22 Correct 146 ms 295584 KB Output is correct
23 Correct 149 ms 295536 KB Output is correct
24 Correct 138 ms 295392 KB Output is correct
25 Correct 152 ms 298616 KB Output is correct
26 Correct 164 ms 298656 KB Output is correct
27 Correct 155 ms 298704 KB Output is correct
28 Correct 166 ms 298180 KB Output is correct
29 Correct 150 ms 299028 KB Output is correct
30 Correct 151 ms 298876 KB Output is correct
31 Correct 148 ms 298760 KB Output is correct
32 Correct 159 ms 298796 KB Output is correct
33 Correct 135 ms 294032 KB Output is correct
34 Correct 141 ms 294016 KB Output is correct
35 Correct 133 ms 294472 KB Output is correct
36 Correct 132 ms 294476 KB Output is correct
37 Correct 135 ms 294220 KB Output is correct
38 Correct 226 ms 319328 KB Output is correct
39 Correct 231 ms 319368 KB Output is correct
40 Correct 212 ms 319260 KB Output is correct
41 Correct 224 ms 319308 KB Output is correct
42 Correct 301 ms 321656 KB Output is correct
43 Correct 285 ms 325836 KB Output is correct
44 Correct 283 ms 321772 KB Output is correct
45 Correct 276 ms 324016 KB Output is correct
46 Correct 225 ms 314276 KB Output is correct
47 Correct 257 ms 315816 KB Output is correct
48 Correct 374 ms 322804 KB Output is correct
49 Correct 369 ms 322984 KB Output is correct
50 Correct 258 ms 315524 KB Output is correct
51 Correct 243 ms 309304 KB Output is correct
52 Correct 344 ms 321060 KB Output is correct
53 Correct 340 ms 321088 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 294424 KB Output is correct
2 Correct 147 ms 294300 KB Output is correct
3 Correct 151 ms 294160 KB Output is correct
4 Correct 145 ms 294092 KB Output is correct
5 Correct 146 ms 294288 KB Output is correct
6 Correct 145 ms 294308 KB Output is correct
7 Correct 148 ms 294264 KB Output is correct
8 Correct 144 ms 294300 KB Output is correct
9 Correct 146 ms 294300 KB Output is correct
10 Correct 152 ms 294044 KB Output is correct
11 Correct 181 ms 294160 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 294032 KB Output is correct
2 Correct 141 ms 294016 KB Output is correct
3 Correct 133 ms 294472 KB Output is correct
4 Correct 132 ms 294476 KB Output is correct
5 Correct 135 ms 294220 KB Output is correct
6 Correct 135 ms 294216 KB Output is correct
7 Correct 737 ms 356664 KB Output is correct
8 Correct 1499 ms 423200 KB Output is correct
9 Correct 1536 ms 423688 KB Output is correct
10 Correct 1518 ms 423884 KB Output is correct
11 Correct 406 ms 342472 KB Output is correct
12 Correct 650 ms 389068 KB Output is correct
13 Correct 668 ms 392100 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 294184 KB Output is correct
2 Correct 133 ms 294544 KB Output is correct
3 Correct 133 ms 294500 KB Output is correct
4 Correct 137 ms 294608 KB Output is correct
5 Correct 135 ms 294584 KB Output is correct
6 Correct 134 ms 294612 KB Output is correct
7 Correct 134 ms 294512 KB Output is correct
8 Correct 131 ms 294188 KB Output is correct
9 Correct 136 ms 294492 KB Output is correct
10 Correct 132 ms 294552 KB Output is correct
11 Correct 136 ms 294504 KB Output is correct
12 Correct 133 ms 294596 KB Output is correct
13 Correct 133 ms 294056 KB Output is correct
14 Correct 140 ms 294132 KB Output is correct
15 Correct 137 ms 294144 KB Output is correct
16 Correct 139 ms 294020 KB Output is correct
17 Correct 134 ms 295560 KB Output is correct
18 Correct 142 ms 295524 KB Output is correct
19 Correct 134 ms 295508 KB Output is correct
20 Correct 137 ms 295476 KB Output is correct
21 Correct 152 ms 295532 KB Output is correct
22 Correct 146 ms 295584 KB Output is correct
23 Correct 149 ms 295536 KB Output is correct
24 Correct 138 ms 295392 KB Output is correct
25 Correct 152 ms 298616 KB Output is correct
26 Correct 164 ms 298656 KB Output is correct
27 Correct 155 ms 298704 KB Output is correct
28 Correct 166 ms 298180 KB Output is correct
29 Correct 150 ms 299028 KB Output is correct
30 Correct 151 ms 298876 KB Output is correct
31 Correct 148 ms 298760 KB Output is correct
32 Correct 159 ms 298796 KB Output is correct
33 Correct 226 ms 319328 KB Output is correct
34 Correct 231 ms 319368 KB Output is correct
35 Correct 212 ms 319260 KB Output is correct
36 Correct 224 ms 319308 KB Output is correct
37 Correct 301 ms 321656 KB Output is correct
38 Correct 285 ms 325836 KB Output is correct
39 Correct 283 ms 321772 KB Output is correct
40 Correct 276 ms 324016 KB Output is correct
41 Correct 225 ms 314276 KB Output is correct
42 Correct 257 ms 315816 KB Output is correct
43 Correct 374 ms 322804 KB Output is correct
44 Correct 369 ms 322984 KB Output is correct
45 Correct 258 ms 315524 KB Output is correct
46 Correct 243 ms 309304 KB Output is correct
47 Correct 344 ms 321060 KB Output is correct
48 Correct 340 ms 321088 KB Output is correct
49 Correct 147 ms 294424 KB Output is correct
50 Correct 147 ms 294300 KB Output is correct
51 Correct 151 ms 294160 KB Output is correct
52 Correct 145 ms 294092 KB Output is correct
53 Correct 146 ms 294288 KB Output is correct
54 Correct 145 ms 294308 KB Output is correct
55 Correct 148 ms 294264 KB Output is correct
56 Correct 144 ms 294300 KB Output is correct
57 Correct 146 ms 294300 KB Output is correct
58 Correct 152 ms 294044 KB Output is correct
59 Correct 181 ms 294160 KB Output is correct
60 Correct 135 ms 294216 KB Output is correct
61 Correct 737 ms 356664 KB Output is correct
62 Correct 1499 ms 423200 KB Output is correct
63 Correct 1536 ms 423688 KB Output is correct
64 Correct 1518 ms 423884 KB Output is correct
65 Correct 406 ms 342472 KB Output is correct
66 Correct 650 ms 389068 KB Output is correct
67 Correct 668 ms 392100 KB Output is correct
68 Correct 135 ms 294032 KB Output is correct
69 Correct 141 ms 294016 KB Output is correct
70 Correct 133 ms 294472 KB Output is correct
71 Correct 132 ms 294476 KB Output is correct
72 Correct 135 ms 294220 KB Output is correct
73 Correct 1674 ms 489948 KB Output is correct
74 Correct 1746 ms 490016 KB Output is correct
75 Correct 1257 ms 490064 KB Output is correct
76 Correct 1202 ms 489928 KB Output is correct
77 Correct 2623 ms 522996 KB Output is correct
78 Correct 2226 ms 440680 KB Output is correct
79 Correct 2470 ms 470580 KB Output is correct
80 Correct 3727 ms 525372 KB Output is correct
81 Correct 2392 ms 471396 KB Output is correct
82 Correct 3563 ms 536684 KB Output is correct
83 Correct 4163 ms 576992 KB Output is correct
84 Correct 1955 ms 450844 KB Output is correct
85 Correct 3373 ms 546436 KB Output is correct
86 Correct 3193 ms 548372 KB Output is correct
87 Correct 1685 ms 508188 KB Output is correct
88 Correct 2604 ms 559968 KB Output is correct
89 Correct 2652 ms 553736 KB Output is correct
90 Correct 2667 ms 552760 KB Output is correct