oj.uz

Submission #823927

# Submission time Handle Problem Language Result Execution time Memory
823927 2023-08-13T10:15:07 Z dxz05 Rectangles (IOI19_rect) C++17
100 / 100
 4840 ms 653124 KB 
// #pragma GCC optimize("Ofast,O3,unroll-loops")
// #pragma GCC target("avx,avx2")

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

inline vector<pair<int, int>> find_borders(const vector<int> &a){
	int n = (int) a.size();

	stack<int> st;
	vector<int> l(n), r(n);
	for (int i = 0; i < n; i++){
		while (!st.empty() && a[st.top()] < a[i]) st.pop();
		l[i] = (st.empty() ? -1 : st.top());
		st.push(i);
	}

	while (!st.empty()) st.pop();

	for (int i = n - 1; i >= 0; i--){
		while (!st.empty() && a[st.top()] < a[i]) st.pop();
		r[i] = (st.empty() ? n : st.top());
		st.push(i);
	}

	vector<pair<int, int>> ans;
	set<pair<int, int>> s1; // (i, r[i])
	set<pair<int, int>> s2; // (r[i], i)
	for (int j = 0; j < n; j++){
		while (!s2.empty()){
			int i = s2.begin()->second;
			if (r[i] < j){
				s1.erase(make_pair(i, r[i]));
				s2.erase(make_pair(r[i], i));
			} else {
				break;
			}
		}

		assert(s1.size() == s2.size());

		auto it = s1.end();
		while (true){
			if (it == s1.begin()) break;
			it--;

			int i = it->first;
			if (i < l[j]) break;

			if (i + 1 < j) ans.emplace_back(i + 1, j - 1);
		}

		s1.emplace(j, r[j]);
		s2.emplace(r[j], j);
	}

	return ans;
}

const int MaxN = 2500;

vector<pair<int, int>> per_col[MaxN][MaxN];
vector<pair<int, int>> per_row[MaxN][MaxN];

vector<tuple<int, int, int>> opening[MaxN];
vector<pair<int, int>> vals_to_add[MaxN];

int fen[MaxN + 1][MaxN + 1];

inline void add(int _x, int _y, int val){
	_x++, _y++;
	int x = _x;
	while (x <= MaxN){
		int y = _y;
		while (y <= MaxN){
			fen[x][y] += val;
			y += (-y & y);
		}
		x += (-x & x);
	}
}

inline int get(int _x, int _y){
	_x++, _y++;
	int res = 0;
	int x = _x;
	while (x > 0){
		int y = _y;
		while (y > 0){
			res += fen[x][y];
			y -= (-y & y);
		}
		x -= (-x & x);
	}
	return res;
}

long long count_rectangles(vector<vector<int>> A) {
	int n = (int) A.size(), m = (int) A[0].size();

	for (int i = 1; i + 1 < n; i++){
		vector<pair<int, int>> f = find_borders(A[i]);

		for (auto [l, r] : f){
			auto &v = per_col[l][r];
			if (v.empty() || v.back().second != i - 1){
				v.emplace_back(i, i);
			} else {
				v.back().second++;
			}
		}
	}

	for (int j = 1; j + 1 < m; j++){
		vector<int> col(n);
		for (int i = 0; i < n; i++) col[i] = A[i][j];
		vector<pair<int, int>> f = find_borders(col);
		for (auto [x, y] : f){
			auto &v = per_row[x][y];
			if (v.empty() || v.back().second != j - 1){
				v.emplace_back(j, j);
			} else {
				v.back().second++;
			}
		}
	}

	for (int x = 0; x < n; x++){
		for (int y = x; y < n; y++){
			for (auto [l, r] : per_row[x][y]){
				opening[l].emplace_back(r, x, y);
			}
		}
	}

	long long ans = 0;
	for (int l = 1; l < m - 1; l++){
		for (auto [r, x, y] : opening[l]){
			vals_to_add[r].emplace_back(x, y);
		}

 		for (int r = m - 2; r >= l; r--){
			for (auto [x, y] : vals_to_add[r]){
				x = n - x - 1;
				add(x, y, 1);
			}

			for (auto [X, Y] : per_col[l][r]){
				X = n - X - 1;
				ans += get(X, Y);
			}

		}

		for (int r = l; r <= m - 2; r++){
			for (auto [x, y] : vals_to_add[r]){
				x = n - x - 1;
				add(x, y, -1);
			}
		}
	}

	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 294128 KB Output is correct
2 Correct 127 ms 294240 KB Output is correct
3 Correct 128 ms 294256 KB Output is correct
4 Correct 126 ms 294256 KB Output is correct
5 Correct 126 ms 293880 KB Output is correct
6 Correct 133 ms 294336 KB Output is correct
7 Correct 134 ms 294316 KB Output is correct
8 Correct 130 ms 294108 KB Output is correct
9 Correct 128 ms 294300 KB Output is correct
10 Correct 127 ms 294348 KB Output is correct
11 Correct 129 ms 294316 KB Output is correct
12 Correct 128 ms 294444 KB Output is correct
13 Correct 128 ms 293828 KB Output is correct
14 Correct 128 ms 293912 KB Output is correct
15 Correct 126 ms 293828 KB Output is correct
16 Correct 129 ms 294092 KB Output is correct
17 Correct 128 ms 293836 KB Output is correct
18 Correct 128 ms 293920 KB Output is correct
19 Correct 129 ms 294336 KB Output is correct
20 Correct 129 ms 293940 KB Output is correct
21 Correct 127 ms 293884 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 294128 KB Output is correct
2 Correct 127 ms 294240 KB Output is correct
3 Correct 128 ms 294256 KB Output is correct
4 Correct 126 ms 294256 KB Output is correct
5 Correct 126 ms 293880 KB Output is correct
6 Correct 133 ms 294336 KB Output is correct
7 Correct 134 ms 294316 KB Output is correct
8 Correct 130 ms 294108 KB Output is correct
9 Correct 128 ms 294300 KB Output is correct
10 Correct 127 ms 294348 KB Output is correct
11 Correct 129 ms 294316 KB Output is correct
12 Correct 128 ms 294444 KB Output is correct
13 Correct 128 ms 293828 KB Output is correct
14 Correct 128 ms 293912 KB Output is correct
15 Correct 126 ms 293828 KB Output is correct
16 Correct 129 ms 294092 KB Output is correct
17 Correct 128 ms 293836 KB Output is correct
18 Correct 128 ms 293920 KB Output is correct
19 Correct 129 ms 294336 KB Output is correct
20 Correct 129 ms 293940 KB Output is correct
21 Correct 127 ms 293884 KB Output is correct
22 Correct 129 ms 294828 KB Output is correct
23 Correct 130 ms 294816 KB Output is correct
24 Correct 131 ms 294824 KB Output is correct
25 Correct 134 ms 294988 KB Output is correct
26 Correct 132 ms 294992 KB Output is correct
27 Correct 131 ms 295012 KB Output is correct
28 Correct 132 ms 294992 KB Output is correct
29 Correct 130 ms 294904 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 294128 KB Output is correct
2 Correct 127 ms 294240 KB Output is correct
3 Correct 128 ms 294256 KB Output is correct
4 Correct 126 ms 294256 KB Output is correct
5 Correct 126 ms 293880 KB Output is correct
6 Correct 133 ms 294336 KB Output is correct
7 Correct 134 ms 294316 KB Output is correct
8 Correct 130 ms 294108 KB Output is correct
9 Correct 128 ms 294300 KB Output is correct
10 Correct 127 ms 294348 KB Output is correct
11 Correct 129 ms 294316 KB Output is correct
12 Correct 128 ms 294444 KB Output is correct
13 Correct 128 ms 293828 KB Output is correct
14 Correct 128 ms 293912 KB Output is correct
15 Correct 126 ms 293828 KB Output is correct
16 Correct 129 ms 294092 KB Output is correct
17 Correct 129 ms 294828 KB Output is correct
18 Correct 130 ms 294816 KB Output is correct
19 Correct 131 ms 294824 KB Output is correct
20 Correct 134 ms 294988 KB Output is correct
21 Correct 132 ms 294992 KB Output is correct
22 Correct 131 ms 295012 KB Output is correct
23 Correct 132 ms 294992 KB Output is correct
24 Correct 130 ms 294904 KB Output is correct
25 Correct 128 ms 293836 KB Output is correct
26 Correct 128 ms 293920 KB Output is correct
27 Correct 129 ms 294336 KB Output is correct
28 Correct 129 ms 293940 KB Output is correct
29 Correct 127 ms 293884 KB Output is correct
30 Correct 147 ms 296328 KB Output is correct
31 Correct 146 ms 296216 KB Output is correct
32 Correct 148 ms 296348 KB Output is correct
33 Correct 142 ms 297036 KB Output is correct
34 Correct 156 ms 298136 KB Output is correct
35 Correct 155 ms 298204 KB Output is correct
36 Correct 154 ms 297780 KB Output is correct
37 Correct 156 ms 297812 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 294128 KB Output is correct
2 Correct 127 ms 294240 KB Output is correct
3 Correct 128 ms 294256 KB Output is correct
4 Correct 126 ms 294256 KB Output is correct
5 Correct 126 ms 293880 KB Output is correct
6 Correct 133 ms 294336 KB Output is correct
7 Correct 134 ms 294316 KB Output is correct
8 Correct 130 ms 294108 KB Output is correct
9 Correct 128 ms 294300 KB Output is correct
10 Correct 127 ms 294348 KB Output is correct
11 Correct 129 ms 294316 KB Output is correct
12 Correct 128 ms 294444 KB Output is correct
13 Correct 128 ms 293828 KB Output is correct
14 Correct 128 ms 293912 KB Output is correct
15 Correct 126 ms 293828 KB Output is correct
16 Correct 129 ms 294092 KB Output is correct
17 Correct 129 ms 294828 KB Output is correct
18 Correct 130 ms 294816 KB Output is correct
19 Correct 131 ms 294824 KB Output is correct
20 Correct 134 ms 294988 KB Output is correct
21 Correct 132 ms 294992 KB Output is correct
22 Correct 131 ms 295012 KB Output is correct
23 Correct 132 ms 294992 KB Output is correct
24 Correct 130 ms 294904 KB Output is correct
25 Correct 147 ms 296328 KB Output is correct
26 Correct 146 ms 296216 KB Output is correct
27 Correct 148 ms 296348 KB Output is correct
28 Correct 142 ms 297036 KB Output is correct
29 Correct 156 ms 298136 KB Output is correct
30 Correct 155 ms 298204 KB Output is correct
31 Correct 154 ms 297780 KB Output is correct
32 Correct 156 ms 297812 KB Output is correct
33 Correct 128 ms 293836 KB Output is correct
34 Correct 128 ms 293920 KB Output is correct
35 Correct 129 ms 294336 KB Output is correct
36 Correct 129 ms 293940 KB Output is correct
37 Correct 127 ms 293884 KB Output is correct
38 Correct 401 ms 326956 KB Output is correct
39 Correct 371 ms 327136 KB Output is correct
40 Correct 370 ms 327188 KB Output is correct
41 Correct 356 ms 327136 KB Output is correct
42 Correct 368 ms 304552 KB Output is correct
43 Correct 362 ms 304428 KB Output is correct
44 Correct 367 ms 304632 KB Output is correct
45 Correct 363 ms 303900 KB Output is correct
46 Correct 289 ms 311444 KB Output is correct
47 Correct 313 ms 312152 KB Output is correct
48 Correct 487 ms 329248 KB Output is correct
49 Correct 488 ms 329272 KB Output is correct
50 Correct 314 ms 315320 KB Output is correct
51 Correct 305 ms 311968 KB Output is correct
52 Correct 458 ms 319820 KB Output is correct
53 Correct 455 ms 319932 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 294408 KB Output is correct
2 Correct 140 ms 294444 KB Output is correct
3 Correct 139 ms 293964 KB Output is correct
4 Correct 129 ms 293940 KB Output is correct
5 Correct 143 ms 294240 KB Output is correct
6 Correct 141 ms 294160 KB Output is correct
7 Correct 141 ms 294220 KB Output is correct
8 Correct 142 ms 294260 KB Output is correct
9 Correct 141 ms 294216 KB Output is correct
10 Correct 139 ms 293888 KB Output is correct
11 Correct 138 ms 293900 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 293836 KB Output is correct
2 Correct 128 ms 293920 KB Output is correct
3 Correct 129 ms 294336 KB Output is correct
4 Correct 129 ms 293940 KB Output is correct
5 Correct 127 ms 293884 KB Output is correct
6 Correct 128 ms 294092 KB Output is correct
7 Correct 1061 ms 369512 KB Output is correct
8 Correct 2138 ms 451676 KB Output is correct
9 Correct 2168 ms 452220 KB Output is correct
10 Correct 2169 ms 452472 KB Output is correct
11 Correct 773 ms 318192 KB Output is correct
12 Correct 1367 ms 340132 KB Output is correct
13 Correct 1460 ms 343124 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 294128 KB Output is correct
2 Correct 127 ms 294240 KB Output is correct
3 Correct 128 ms 294256 KB Output is correct
4 Correct 126 ms 294256 KB Output is correct
5 Correct 126 ms 293880 KB Output is correct
6 Correct 133 ms 294336 KB Output is correct
7 Correct 134 ms 294316 KB Output is correct
8 Correct 130 ms 294108 KB Output is correct
9 Correct 128 ms 294300 KB Output is correct
10 Correct 127 ms 294348 KB Output is correct
11 Correct 129 ms 294316 KB Output is correct
12 Correct 128 ms 294444 KB Output is correct
13 Correct 128 ms 293828 KB Output is correct
14 Correct 128 ms 293912 KB Output is correct
15 Correct 126 ms 293828 KB Output is correct
16 Correct 129 ms 294092 KB Output is correct
17 Correct 129 ms 294828 KB Output is correct
18 Correct 130 ms 294816 KB Output is correct
19 Correct 131 ms 294824 KB Output is correct
20 Correct 134 ms 294988 KB Output is correct
21 Correct 132 ms 294992 KB Output is correct
22 Correct 131 ms 295012 KB Output is correct
23 Correct 132 ms 294992 KB Output is correct
24 Correct 130 ms 294904 KB Output is correct
25 Correct 147 ms 296328 KB Output is correct
26 Correct 146 ms 296216 KB Output is correct
27 Correct 148 ms 296348 KB Output is correct
28 Correct 142 ms 297036 KB Output is correct
29 Correct 156 ms 298136 KB Output is correct
30 Correct 155 ms 298204 KB Output is correct
31 Correct 154 ms 297780 KB Output is correct
32 Correct 156 ms 297812 KB Output is correct
33 Correct 401 ms 326956 KB Output is correct
34 Correct 371 ms 327136 KB Output is correct
35 Correct 370 ms 327188 KB Output is correct
36 Correct 356 ms 327136 KB Output is correct
37 Correct 368 ms 304552 KB Output is correct
38 Correct 362 ms 304428 KB Output is correct
39 Correct 367 ms 304632 KB Output is correct
40 Correct 363 ms 303900 KB Output is correct
41 Correct 289 ms 311444 KB Output is correct
42 Correct 313 ms 312152 KB Output is correct
43 Correct 487 ms 329248 KB Output is correct
44 Correct 488 ms 329272 KB Output is correct
45 Correct 314 ms 315320 KB Output is correct
46 Correct 305 ms 311968 KB Output is correct
47 Correct 458 ms 319820 KB Output is correct
48 Correct 455 ms 319932 KB Output is correct
49 Correct 144 ms 294408 KB Output is correct
50 Correct 140 ms 294444 KB Output is correct
51 Correct 139 ms 293964 KB Output is correct
52 Correct 129 ms 293940 KB Output is correct
53 Correct 143 ms 294240 KB Output is correct
54 Correct 141 ms 294160 KB Output is correct
55 Correct 141 ms 294220 KB Output is correct
56 Correct 142 ms 294260 KB Output is correct
57 Correct 141 ms 294216 KB Output is correct
58 Correct 139 ms 293888 KB Output is correct
59 Correct 138 ms 293900 KB Output is correct
60 Correct 128 ms 294092 KB Output is correct
61 Correct 1061 ms 369512 KB Output is correct
62 Correct 2138 ms 451676 KB Output is correct
63 Correct 2168 ms 452220 KB Output is correct
64 Correct 2169 ms 452472 KB Output is correct
65 Correct 773 ms 318192 KB Output is correct
66 Correct 1367 ms 340132 KB Output is correct
67 Correct 1460 ms 343124 KB Output is correct
68 Correct 128 ms 293836 KB Output is correct
69 Correct 128 ms 293920 KB Output is correct
70 Correct 129 ms 294336 KB Output is correct
71 Correct 129 ms 293940 KB Output is correct
72 Correct 127 ms 293884 KB Output is correct
73 Correct 4009 ms 642544 KB Output is correct
74 Correct 3528 ms 638960 KB Output is correct
75 Correct 3525 ms 633656 KB Output is correct
76 Correct 3028 ms 632972 KB Output is correct
77 Correct 2966 ms 353540 KB Output is correct
78 Correct 2871 ms 520164 KB Output is correct
79 Correct 3076 ms 525800 KB Output is correct
80 Correct 4658 ms 629996 KB Output is correct
81 Correct 3000 ms 513476 KB Output is correct
82 Correct 3986 ms 596692 KB Output is correct
83 Correct 4840 ms 653124 KB Output is correct
84 Correct 2711 ms 470952 KB Output is correct
85 Correct 4503 ms 572752 KB Output is correct
86 Correct 4324 ms 574704 KB Output is correct
87 Correct 1780 ms 343728 KB Output is correct
88 Correct 2961 ms 368180 KB Output is correct
89 Correct 2960 ms 368292 KB Output is correct
90 Correct 2968 ms 367776 KB Output is correct