oj.uz

Submission #266823

# Submission time Handle Problem Language Result Execution time Memory
266823 2020-08-15T13:12:35 Z dennisstar Rectangles (IOI19_rect) C++17
100 / 100
 4886 ms 362800 KB 
#include <bits/stdc++.h>
#include "rect.h"
#define eb emplace_back
#define hsh(b, c) ((b)*2500+(c))
using namespace std;

int N, M;
vector<int> H[2505], V[2505];

long long count_rectangles(vector<vector<int>> a) {
	N=a.size(); M=a[0].size();
	vector<vector<int>> l, r, u, d;
	for (int i=0; i<N; i++)
		l.eb(vector<int>(M, -1));
	r=u=d=l;

	for (int i=1; i<N-1; i++) {
		vector<int> st;
		for (int j=0; j<M; j++) {
			while (st.size()&&a[i][st.back()]<a[i][j]) st.pop_back();
			if (st.size()&&st.back()<j-1) H[st.back()].eb(hsh(j, i));
			st.eb(j);
		}
		st.clear();
		for (int j=M-1; j>=0; j--) {
			while (st.size()&&a[i][st.back()]<a[i][j]) st.pop_back();
			if (st.size()&&st.back()>j+1&&a[i][st.back()]!=a[i][j]) H[j].eb(hsh(st.back(), i));
			st.eb(j);
		}
		st.clear();
		for (int j=0; j<M; j++) {
			while (st.size()&&a[i][st.back()]<=a[i][j]) st.pop_back();
			if (st.size()) l[i][j]=st.back();
			st.eb(j);
		}
		st.clear();
		for (int j=M-1; j>=0; j--) {
			while (st.size()&&a[i][st.back()]<=a[i][j]) st.pop_back();
			if (st.size()) r[i][j]=st.back();
			st.eb(j);
		}
	}

	for (int j=1; j<M-1; j++) {
		vector<int> st;
		for (int i=0; i<N; i++) {
			while (st.size()&&a[st.back()][j]<a[i][j]) st.pop_back();
			if (st.size()&&st.back()<i-1) V[st.back()].eb(hsh(i, j));
			st.eb(i);
		}
		st.clear();
		for (int i=N-1; i>=0; i--) {
			while (st.size()&&a[st.back()][j]<a[i][j]) st.pop_back();
			if (st.size()&&st.back()>i+1&&a[st.back()][j]!=a[i][j]) V[i].eb(hsh(st.back(), j));
			st.eb(i);
		}
		st.clear();
		for (int i=0; i<N; i++) {
			while (st.size()&&a[st.back()][j]<=a[i][j]) st.pop_back();
			if (st.size()) u[i][j]=st.back();
			st.eb(i);
		}
		st.clear();
		for (int i=N-1; i>=0; i--) {
			while (st.size()&&a[st.back()][j]<=a[i][j]) st.pop_back();
			if (st.size()) d[i][j]=st.back();
			st.eb(i);
		}
	}

	for (int i=0; i<M; i++) sort(H[i].begin(), H[i].end());
	for (int i=0; i<N; i++) sort(V[i].begin(), V[i].end());

	vector<tuple<int, int, int, int>> A;
	for (int i=1; i<N-1; i++) for (int j=1; j<M-1; j++) {
		int L=l[i][j], R=r[i][j], U=u[i][j], D=d[i][j];
		if (L==-1||R==-1||U==-1||D==-1) continue;

		int b1=lower_bound(H[L].begin(), H[L].end(), hsh(R, U+1))-H[L].begin();
		if (b1>=H[L].size()||hsh(R, U+1)!=H[L][b1]) continue;
		b1+=D-U-2;
		if (b1>=H[L].size()||hsh(R, D-1)!=H[L][b1]) continue;

		b1=lower_bound(V[U].begin(), V[U].end(), hsh(D, L+1))-V[U].begin();
		if (b1>=V[U].size()||hsh(D, L+1)!=V[U][b1]) continue;
		b1+=R-L-2;
		if (b1>=V[U].size()||hsh(D, R-1)!=V[U][b1]) continue;

		A.eb(L, R, U, D);
	}

	sort(A.begin(), A.end());
	return unique(A.begin(), A.end())-A.begin();
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:80:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   if (b1>=H[L].size()||hsh(R, U+1)!=H[L][b1]) continue;
      |       ~~^~~~~~~~~~~~~
rect.cpp:82:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   if (b1>=H[L].size()||hsh(R, D-1)!=H[L][b1]) continue;
      |       ~~^~~~~~~~~~~~~
rect.cpp:85:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   if (b1>=V[U].size()||hsh(D, L+1)!=V[U][b1]) continue;
      |       ~~^~~~~~~~~~~~~
rect.cpp:87:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   if (b1>=V[U].size()||hsh(D, R-1)!=V[U][b1]) continue;
      |       ~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 3 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 3 ms 640 KB Output is correct
21 Correct 3 ms 768 KB Output is correct
22 Correct 5 ms 768 KB Output is correct
23 Correct 4 ms 768 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 0 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 512 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 3 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 3 ms 640 KB Output is correct
21 Correct 3 ms 768 KB Output is correct
22 Correct 5 ms 768 KB Output is correct
23 Correct 4 ms 768 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 16 ms 3196 KB Output is correct
26 Correct 15 ms 3196 KB Output is correct
27 Correct 15 ms 3324 KB Output is correct
28 Correct 11 ms 1920 KB Output is correct
29 Correct 17 ms 2432 KB Output is correct
30 Correct 20 ms 2560 KB Output is correct
31 Correct 18 ms 2820 KB Output is correct
32 Correct 18 ms 2560 KB Output is correct
33 Correct 0 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 512 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 3 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 3 ms 640 KB Output is correct
21 Correct 3 ms 768 KB Output is correct
22 Correct 5 ms 768 KB Output is correct
23 Correct 4 ms 768 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 16 ms 3196 KB Output is correct
26 Correct 15 ms 3196 KB Output is correct
27 Correct 15 ms 3324 KB Output is correct
28 Correct 11 ms 1920 KB Output is correct
29 Correct 17 ms 2432 KB Output is correct
30 Correct 20 ms 2560 KB Output is correct
31 Correct 18 ms 2820 KB Output is correct
32 Correct 18 ms 2560 KB Output is correct
33 Correct 73 ms 17312 KB Output is correct
34 Correct 78 ms 17400 KB Output is correct
35 Correct 71 ms 17272 KB Output is correct
36 Correct 75 ms 17400 KB Output is correct
37 Correct 193 ms 28384 KB Output is correct
38 Correct 196 ms 28388 KB Output is correct
39 Correct 197 ms 28900 KB Output is correct
40 Correct 183 ms 27756 KB Output is correct
41 Correct 112 ms 15352 KB Output is correct
42 Correct 148 ms 17144 KB Output is correct
43 Correct 234 ms 24172 KB Output is correct
44 Correct 247 ms 25196 KB Output is correct
45 Correct 119 ms 13428 KB Output is correct
46 Correct 125 ms 13548 KB Output is correct
47 Correct 258 ms 24468 KB Output is correct
48 Correct 254 ms 25068 KB Output is correct
49 Correct 0 ms 384 KB Output is correct
50 Correct 1 ms 384 KB Output is correct
51 Correct 1 ms 512 KB Output is correct
52 Correct 1 ms 384 KB Output is correct
53 Correct 1 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 548 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 876 ms 86064 KB Output is correct
3 Correct 2025 ms 181992 KB Output is correct
4 Correct 2177 ms 180708 KB Output is correct
5 Correct 2001 ms 180720 KB Output is correct
6 Correct 422 ms 74152 KB Output is correct
7 Correct 955 ms 140792 KB Output is correct
8 Correct 994 ms 149880 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 3 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 3 ms 640 KB Output is correct
21 Correct 3 ms 768 KB Output is correct
22 Correct 5 ms 768 KB Output is correct
23 Correct 4 ms 768 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 16 ms 3196 KB Output is correct
26 Correct 15 ms 3196 KB Output is correct
27 Correct 15 ms 3324 KB Output is correct
28 Correct 11 ms 1920 KB Output is correct
29 Correct 17 ms 2432 KB Output is correct
30 Correct 20 ms 2560 KB Output is correct
31 Correct 18 ms 2820 KB Output is correct
32 Correct 18 ms 2560 KB Output is correct
33 Correct 73 ms 17312 KB Output is correct
34 Correct 78 ms 17400 KB Output is correct
35 Correct 71 ms 17272 KB Output is correct
36 Correct 75 ms 17400 KB Output is correct
37 Correct 193 ms 28384 KB Output is correct
38 Correct 196 ms 28388 KB Output is correct
39 Correct 197 ms 28900 KB Output is correct
40 Correct 183 ms 27756 KB Output is correct
41 Correct 112 ms 15352 KB Output is correct
42 Correct 148 ms 17144 KB Output is correct
43 Correct 234 ms 24172 KB Output is correct
44 Correct 247 ms 25196 KB Output is correct
45 Correct 119 ms 13428 KB Output is correct
46 Correct 125 ms 13548 KB Output is correct
47 Correct 258 ms 24468 KB Output is correct
48 Correct 254 ms 25068 KB Output is correct
49 Correct 2 ms 896 KB Output is correct
50 Correct 2 ms 768 KB Output is correct
51 Correct 1 ms 640 KB Output is correct
52 Correct 1 ms 384 KB Output is correct
53 Correct 2 ms 768 KB Output is correct
54 Correct 3 ms 768 KB Output is correct
55 Correct 3 ms 768 KB Output is correct
56 Correct 2 ms 768 KB Output is correct
57 Correct 2 ms 768 KB Output is correct
58 Correct 1 ms 512 KB Output is correct
59 Correct 1 ms 548 KB Output is correct
60 Correct 1 ms 384 KB Output is correct
61 Correct 876 ms 86064 KB Output is correct
62 Correct 2025 ms 181992 KB Output is correct
63 Correct 2177 ms 180708 KB Output is correct
64 Correct 2001 ms 180720 KB Output is correct
65 Correct 422 ms 74152 KB Output is correct
66 Correct 955 ms 140792 KB Output is correct
67 Correct 994 ms 149880 KB Output is correct
68 Correct 1372 ms 183872 KB Output is correct
69 Correct 1322 ms 183544 KB Output is correct
70 Correct 1332 ms 183296 KB Output is correct
71 Correct 1332 ms 182580 KB Output is correct
72 Correct 3508 ms 355116 KB Output is correct
73 Correct 2457 ms 168020 KB Output is correct
74 Correct 2513 ms 172360 KB Output is correct
75 Correct 4528 ms 293144 KB Output is correct
76 Correct 2611 ms 172624 KB Output is correct
77 Correct 3247 ms 214040 KB Output is correct
78 Correct 4539 ms 302124 KB Output is correct
79 Correct 2725 ms 169580 KB Output is correct
80 Correct 4886 ms 293184 KB Output is correct
81 Correct 4586 ms 286224 KB Output is correct
82 Correct 1931 ms 202240 KB Output is correct
83 Correct 3484 ms 362588 KB Output is correct
84 Correct 3405 ms 362800 KB Output is correct
85 Correct 3411 ms 362692 KB Output is correct
86 Correct 0 ms 384 KB Output is correct
87 Correct 1 ms 384 KB Output is correct
88 Correct 1 ms 512 KB Output is correct
89 Correct 1 ms 384 KB Output is correct
90 Correct 1 ms 384 KB Output is correct