oj.uz

Submission #779224

# Submission time Handle Problem Language Result Execution time Memory
779224 2023-07-11T09:15:01 Z ieeqwq Rectangles (IOI19_rect) C++17
100 / 100
 2375 ms 931836 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "rect.h"
using namespace std;
using LL = long long;
int fenwick[2500];
inline void modify(int x, int v) {
	for (int i = x + 1; i; i -= i & -i) {
		fenwick[i - 1] += v;
	}
}
inline int get(int x) {
	int r = 0;
	for (int i = x + 1; i <= 2500; i += i & -i) {
		r += fenwick[i - 1];
	}
	return r;
}
struct DS {
	vector<array<int, 2>> p, q;
	DS() = default;
	void insert(int x, int y) {
		p.push_back({x, y});
	}
	void query(int x, int y) {
		q.push_back({x, y});
	}
	int solve() {
		int res = 0;
		sort(p.begin(), p.end()), sort(q.begin(), q.end());
		int idx = 0;
		for (const auto &[x, y] : q) {
			while (idx < p.size() && p[idx][0] <= x) {
				modify(p[idx++][1], 1);
			}
			res += get(y);
		}
		while (idx) {
			modify(p[--idx][1], -1);
		}
		return res;
	}
} d[2500][2500];
vector<array<int, 2>> avc[2500], avr[2500];
vector<int> down[2500], rght[2500];
int lef[2500], rgt[2500];
int Where[2500][2500];
LL count_rectangles(vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	for (int r = 1; r <= n - 2; r++) {
		{
			stack<int> st;
			for (int c = 1; c <= m - 2; c++) {
				while (st.size() && a[r][st.top()] <= a[r][c]) {
					st.pop();
				}
				if (st.empty()) {
					lef[c] = 1;
				} else {
					lef[c] = st.top() + 1;
				}
				st.push(c);
			}
		}
		{
			stack<int> st;
			for (int c = m - 2; c >= 1; c--) {
				while (st.size() && a[r][st.top()] < a[r][c]) {
					st.pop();
				}
				if (st.empty()) {
					rgt[c] = m - 2;
				} else {
					rgt[c] = st.top() - 1;
				}
				st.push(c);
			}
		}
		for (int i = 1; i <= m - 2; i++) {
			if (a[r][i] < min(a[r][lef[i] - 1], a[r][rgt[i] + 1])) {
				avc[r].push_back({lef[i], rgt[i]});
			}
		}
	}
	for (int c = 1; c <= m - 2; c++) {
		{
			stack<int> st;
			for (int r = 1; r <= n - 2; r++) {
				while (st.size() && a[st.top()][c] <= a[r][c]) {
					st.pop();
				}
				if (st.empty()) {
					lef[r] = 1;
				} else {
					lef[r] = st.top() + 1;
				}
				st.push(r);
			}
		}
		{
			stack<int> st;
			for (int r = n - 2; r >= 1; r--) {
				while (st.size() && a[st.top()][c] < a[r][c]) {
					st.pop();
				}
				if (st.empty()) {
					rgt[r] = n - 2;
				} else {
					rgt[r] = st.top() - 1;
				}
				st.push(r);
			}
		}
		for (int i = 1; i <= n - 2; i++) {
			if (a[i][c] < min(a[lef[i] - 1][c], a[rgt[i] + 1][c])) {
				avr[c].push_back({lef[i], rgt[i]});
			}
		}
	}
	memset(Where, -1, sizeof Where);
	for (int i = n - 2; i >= 1; i--) {
		down[i].resize(avc[i].size());
		for (int j = 0; j < avc[i + 1].size(); j++) {
			auto [x, y] = avc[i + 1][j];
			Where[x][y] = j;
		}
		for (int j = 0; j < avc[i].size(); j++) {
			auto it = avc[i][j];
			int where = Where[it[0]][it[1]];
			if (where == -1 || i == n - 2) {
				down[i][j] = i;
			} else {
				down[i][j] = down[i + 1][where];
			}
		}
		for (auto [x, y] : avc[i + 1]) {
			Where[x][y] = -1;
		}
	}
	for (int i = m - 2; i >= 1; i--) {
		rght[i].resize(avr[i].size());
		for (int j = 0; j < avr[i + 1].size(); j++) {
			auto [x, y] = avr[i + 1][j];
			Where[x][y] = j;
		}
		for (int j = 0; j < avr[i].size(); j++) {
			auto it = avr[i][j];
			int where = Where[it[0]][it[1]];
			if (where == -1) {
				rght[i][j] = i;
			} else {
				rght[i][j] = rght[i + 1][where];
			}
		}
		for (auto [x, y] : avr[i + 1]) {
			Where[x][y] = -1;
		}
	}
	for (int c = 1; c <= m - 2; c++) {
		for (int i = 0; i < avr[c].size(); i++) {
			auto [L, R] = avr[c][i];
			d[L][c].insert(R, rght[c][i]);
		}
	}
	for (int r = 1; r <= n - 2; r++) {
		for (int i = 0; i < avc[r].size(); i++) {
			auto [L, R] = avc[r][i];
			d[r][L].query(down[r][i], R);
		}
	}
	LL ans = 0;
	for (int i = 1; i <= n - 2; i++) {
		for (int j = 1; j <= m - 2; j++) {
			ans += d[i][j].solve();
		}
	}
	return ans;
}

Compilation message

rect.cpp: In member function 'int DS::solve()':
rect.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    while (idx < p.size() && p[idx][0] <= x) {
      |           ~~~~^~~~~~~~~~
rect.cpp: In function 'LL count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:123:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for (int j = 0; j < avc[i + 1].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:127:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for (int j = 0; j < avc[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
rect.cpp:142:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   for (int j = 0; j < avr[i + 1].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:146:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for (int j = 0; j < avr[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
rect.cpp:160:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |   for (int i = 0; i < avr[c].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
rect.cpp:166:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |   for (int i = 0; i < avc[r].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 318432 KB Output is correct
2 Correct 125 ms 318600 KB Output is correct
3 Correct 125 ms 318532 KB Output is correct
4 Correct 128 ms 318612 KB Output is correct
5 Correct 128 ms 318564 KB Output is correct
6 Correct 132 ms 318556 KB Output is correct
7 Correct 125 ms 318536 KB Output is correct
8 Correct 127 ms 318536 KB Output is correct
9 Correct 125 ms 318512 KB Output is correct
10 Correct 138 ms 318480 KB Output is correct
11 Correct 127 ms 318500 KB Output is correct
12 Correct 128 ms 318500 KB Output is correct
13 Correct 127 ms 318412 KB Output is correct
14 Correct 127 ms 318492 KB Output is correct
15 Correct 126 ms 318456 KB Output is correct
16 Correct 127 ms 318428 KB Output is correct
17 Correct 129 ms 318488 KB Output is correct
18 Correct 132 ms 318432 KB Output is correct
19 Correct 126 ms 318540 KB Output is correct
20 Correct 129 ms 318432 KB Output is correct
21 Correct 127 ms 318536 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 318432 KB Output is correct
2 Correct 125 ms 318600 KB Output is correct
3 Correct 125 ms 318532 KB Output is correct
4 Correct 128 ms 318612 KB Output is correct
5 Correct 128 ms 318564 KB Output is correct
6 Correct 132 ms 318556 KB Output is correct
7 Correct 125 ms 318536 KB Output is correct
8 Correct 127 ms 318536 KB Output is correct
9 Correct 125 ms 318512 KB Output is correct
10 Correct 138 ms 318480 KB Output is correct
11 Correct 127 ms 318500 KB Output is correct
12 Correct 128 ms 318500 KB Output is correct
13 Correct 127 ms 318412 KB Output is correct
14 Correct 127 ms 318492 KB Output is correct
15 Correct 126 ms 318456 KB Output is correct
16 Correct 127 ms 318428 KB Output is correct
17 Correct 129 ms 318488 KB Output is correct
18 Correct 132 ms 318432 KB Output is correct
19 Correct 126 ms 318540 KB Output is correct
20 Correct 129 ms 318432 KB Output is correct
21 Correct 127 ms 318536 KB Output is correct
22 Correct 128 ms 319188 KB Output is correct
23 Correct 128 ms 319104 KB Output is correct
24 Correct 129 ms 319132 KB Output is correct
25 Correct 125 ms 318720 KB Output is correct
26 Correct 133 ms 318932 KB Output is correct
27 Correct 127 ms 319004 KB Output is correct
28 Correct 135 ms 318924 KB Output is correct
29 Correct 129 ms 318724 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 318432 KB Output is correct
2 Correct 125 ms 318600 KB Output is correct
3 Correct 125 ms 318532 KB Output is correct
4 Correct 128 ms 318612 KB Output is correct
5 Correct 128 ms 318564 KB Output is correct
6 Correct 132 ms 318556 KB Output is correct
7 Correct 125 ms 318536 KB Output is correct
8 Correct 127 ms 318536 KB Output is correct
9 Correct 125 ms 318512 KB Output is correct
10 Correct 138 ms 318480 KB Output is correct
11 Correct 127 ms 318500 KB Output is correct
12 Correct 128 ms 318500 KB Output is correct
13 Correct 127 ms 318412 KB Output is correct
14 Correct 127 ms 318492 KB Output is correct
15 Correct 126 ms 318456 KB Output is correct
16 Correct 127 ms 318428 KB Output is correct
17 Correct 128 ms 319188 KB Output is correct
18 Correct 128 ms 319104 KB Output is correct
19 Correct 129 ms 319132 KB Output is correct
20 Correct 125 ms 318720 KB Output is correct
21 Correct 133 ms 318932 KB Output is correct
22 Correct 127 ms 319004 KB Output is correct
23 Correct 135 ms 318924 KB Output is correct
24 Correct 129 ms 318724 KB Output is correct
25 Correct 129 ms 318488 KB Output is correct
26 Correct 132 ms 318432 KB Output is correct
27 Correct 126 ms 318540 KB Output is correct
28 Correct 129 ms 318432 KB Output is correct
29 Correct 127 ms 318536 KB Output is correct
30 Correct 139 ms 322636 KB Output is correct
31 Correct 134 ms 322652 KB Output is correct
32 Correct 136 ms 322664 KB Output is correct
33 Correct 138 ms 320228 KB Output is correct
34 Correct 142 ms 321484 KB Output is correct
35 Correct 144 ms 321748 KB Output is correct
36 Correct 137 ms 321464 KB Output is correct
37 Correct 137 ms 321504 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 318432 KB Output is correct
2 Correct 125 ms 318600 KB Output is correct
3 Correct 125 ms 318532 KB Output is correct
4 Correct 128 ms 318612 KB Output is correct
5 Correct 128 ms 318564 KB Output is correct
6 Correct 132 ms 318556 KB Output is correct
7 Correct 125 ms 318536 KB Output is correct
8 Correct 127 ms 318536 KB Output is correct
9 Correct 125 ms 318512 KB Output is correct
10 Correct 138 ms 318480 KB Output is correct
11 Correct 127 ms 318500 KB Output is correct
12 Correct 128 ms 318500 KB Output is correct
13 Correct 127 ms 318412 KB Output is correct
14 Correct 127 ms 318492 KB Output is correct
15 Correct 126 ms 318456 KB Output is correct
16 Correct 127 ms 318428 KB Output is correct
17 Correct 128 ms 319188 KB Output is correct
18 Correct 128 ms 319104 KB Output is correct
19 Correct 129 ms 319132 KB Output is correct
20 Correct 125 ms 318720 KB Output is correct
21 Correct 133 ms 318932 KB Output is correct
22 Correct 127 ms 319004 KB Output is correct
23 Correct 135 ms 318924 KB Output is correct
24 Correct 129 ms 318724 KB Output is correct
25 Correct 139 ms 322636 KB Output is correct
26 Correct 134 ms 322652 KB Output is correct
27 Correct 136 ms 322664 KB Output is correct
28 Correct 138 ms 320228 KB Output is correct
29 Correct 142 ms 321484 KB Output is correct
30 Correct 144 ms 321748 KB Output is correct
31 Correct 137 ms 321464 KB Output is correct
32 Correct 137 ms 321504 KB Output is correct
33 Correct 129 ms 318488 KB Output is correct
34 Correct 132 ms 318432 KB Output is correct
35 Correct 126 ms 318540 KB Output is correct
36 Correct 129 ms 318432 KB Output is correct
37 Correct 127 ms 318536 KB Output is correct
38 Correct 191 ms 348452 KB Output is correct
39 Correct 188 ms 343740 KB Output is correct
40 Correct 179 ms 343628 KB Output is correct
41 Correct 181 ms 338936 KB Output is correct
42 Correct 216 ms 371124 KB Output is correct
43 Correct 218 ms 371132 KB Output is correct
44 Correct 223 ms 371456 KB Output is correct
45 Correct 213 ms 368540 KB Output is correct
46 Correct 199 ms 334808 KB Output is correct
47 Correct 207 ms 340488 KB Output is correct
48 Correct 270 ms 357068 KB Output is correct
49 Correct 283 ms 359092 KB Output is correct
50 Correct 203 ms 338712 KB Output is correct
51 Correct 220 ms 338780 KB Output is correct
52 Correct 264 ms 356044 KB Output is correct
53 Correct 278 ms 357236 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 318988 KB Output is correct
2 Correct 126 ms 318880 KB Output is correct
3 Correct 127 ms 318580 KB Output is correct
4 Correct 124 ms 318412 KB Output is correct
5 Correct 127 ms 318784 KB Output is correct
6 Correct 138 ms 318728 KB Output is correct
7 Correct 127 ms 318820 KB Output is correct
8 Correct 144 ms 318788 KB Output is correct
9 Correct 127 ms 318792 KB Output is correct
10 Correct 127 ms 318456 KB Output is correct
11 Correct 127 ms 318536 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 318488 KB Output is correct
2 Correct 132 ms 318432 KB Output is correct
3 Correct 126 ms 318540 KB Output is correct
4 Correct 129 ms 318432 KB Output is correct
5 Correct 127 ms 318536 KB Output is correct
6 Correct 128 ms 318476 KB Output is correct
7 Correct 513 ms 416128 KB Output is correct
8 Correct 1106 ms 528560 KB Output is correct
9 Correct 1074 ms 529396 KB Output is correct
10 Correct 1099 ms 529380 KB Output is correct
11 Correct 244 ms 348824 KB Output is correct
12 Correct 419 ms 376060 KB Output is correct
13 Correct 428 ms 379336 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 318432 KB Output is correct
2 Correct 125 ms 318600 KB Output is correct
3 Correct 125 ms 318532 KB Output is correct
4 Correct 128 ms 318612 KB Output is correct
5 Correct 128 ms 318564 KB Output is correct
6 Correct 132 ms 318556 KB Output is correct
7 Correct 125 ms 318536 KB Output is correct
8 Correct 127 ms 318536 KB Output is correct
9 Correct 125 ms 318512 KB Output is correct
10 Correct 138 ms 318480 KB Output is correct
11 Correct 127 ms 318500 KB Output is correct
12 Correct 128 ms 318500 KB Output is correct
13 Correct 127 ms 318412 KB Output is correct
14 Correct 127 ms 318492 KB Output is correct
15 Correct 126 ms 318456 KB Output is correct
16 Correct 127 ms 318428 KB Output is correct
17 Correct 128 ms 319188 KB Output is correct
18 Correct 128 ms 319104 KB Output is correct
19 Correct 129 ms 319132 KB Output is correct
20 Correct 125 ms 318720 KB Output is correct
21 Correct 133 ms 318932 KB Output is correct
22 Correct 127 ms 319004 KB Output is correct
23 Correct 135 ms 318924 KB Output is correct
24 Correct 129 ms 318724 KB Output is correct
25 Correct 139 ms 322636 KB Output is correct
26 Correct 134 ms 322652 KB Output is correct
27 Correct 136 ms 322664 KB Output is correct
28 Correct 138 ms 320228 KB Output is correct
29 Correct 142 ms 321484 KB Output is correct
30 Correct 144 ms 321748 KB Output is correct
31 Correct 137 ms 321464 KB Output is correct
32 Correct 137 ms 321504 KB Output is correct
33 Correct 191 ms 348452 KB Output is correct
34 Correct 188 ms 343740 KB Output is correct
35 Correct 179 ms 343628 KB Output is correct
36 Correct 181 ms 338936 KB Output is correct
37 Correct 216 ms 371124 KB Output is correct
38 Correct 218 ms 371132 KB Output is correct
39 Correct 223 ms 371456 KB Output is correct
40 Correct 213 ms 368540 KB Output is correct
41 Correct 199 ms 334808 KB Output is correct
42 Correct 207 ms 340488 KB Output is correct
43 Correct 270 ms 357068 KB Output is correct
44 Correct 283 ms 359092 KB Output is correct
45 Correct 203 ms 338712 KB Output is correct
46 Correct 220 ms 338780 KB Output is correct
47 Correct 264 ms 356044 KB Output is correct
48 Correct 278 ms 357236 KB Output is correct
49 Correct 126 ms 318988 KB Output is correct
50 Correct 126 ms 318880 KB Output is correct
51 Correct 127 ms 318580 KB Output is correct
52 Correct 124 ms 318412 KB Output is correct
53 Correct 127 ms 318784 KB Output is correct
54 Correct 138 ms 318728 KB Output is correct
55 Correct 127 ms 318820 KB Output is correct
56 Correct 144 ms 318788 KB Output is correct
57 Correct 127 ms 318792 KB Output is correct
58 Correct 127 ms 318456 KB Output is correct
59 Correct 127 ms 318536 KB Output is correct
60 Correct 128 ms 318476 KB Output is correct
61 Correct 513 ms 416128 KB Output is correct
62 Correct 1106 ms 528560 KB Output is correct
63 Correct 1074 ms 529396 KB Output is correct
64 Correct 1099 ms 529380 KB Output is correct
65 Correct 244 ms 348824 KB Output is correct
66 Correct 419 ms 376060 KB Output is correct
67 Correct 428 ms 379336 KB Output is correct
68 Correct 129 ms 318488 KB Output is correct
69 Correct 132 ms 318432 KB Output is correct
70 Correct 126 ms 318540 KB Output is correct
71 Correct 129 ms 318432 KB Output is correct
72 Correct 127 ms 318536 KB Output is correct
73 Correct 1056 ms 660504 KB Output is correct
74 Correct 1205 ms 591656 KB Output is correct
75 Correct 916 ms 591780 KB Output is correct
76 Correct 813 ms 523932 KB Output is correct
77 Correct 2373 ms 931836 KB Output is correct
78 Correct 1380 ms 590600 KB Output is correct
79 Correct 1493 ms 604108 KB Output is correct
80 Correct 2129 ms 762320 KB Output is correct
81 Correct 1316 ms 593192 KB Output is correct
82 Correct 1746 ms 672036 KB Output is correct
83 Correct 2229 ms 768744 KB Output is correct
84 Correct 1284 ms 573264 KB Output is correct
85 Correct 2155 ms 742892 KB Output is correct
86 Correct 2061 ms 729060 KB Output is correct
87 Correct 1167 ms 688592 KB Output is correct
88 Correct 2375 ms 926664 KB Output is correct
89 Correct 2332 ms 926912 KB Output is correct
90 Correct 2338 ms 926156 KB Output is correct