# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
925558 |
2024-02-12T04:31:09 Z |
hmm789 |
Rectangles (IOI19_rect) |
C++14 |
|
3097 ms |
965884 KB |
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define INF 1000000000000000000
#define MOD 998244353
int fw[2505];
void update(int x, int v) {
for(x++; x < 2505; x += x&-x) fw[x] += v;
}
void update(int x, int y, int v) {
update(x, v); update(y+1, -v);
}
int query(int x) {
int ans = 0;
for(x++; x; x -= x&-x) ans += fw[x];
return ans;
}
long long count_rectangles(vector<vector<int>> a) {
int m = a.size(), n = a[0].size();
vector<int> tot[max(n,m)][max(n,m)];
vector<pair<int, int>> goodh[m][n], goodv[m][n];
for(int i = 1; i < m-1; i++) {
stack<int> s;
int l[n], r[n];
for(int j = 0; j < n; j++) {
while(s.size() && a[i][s.top()] <= a[i][j]) s.pop();
if(s.size()) l[j] = s.top();
else l[j] = -1;
s.push(j);
}
while(s.size()) s.pop();
for(int j = n-1; j >= 0; j--) {
while(s.size() && a[i][s.top()] <= a[i][j]) s.pop();
if(s.size()) r[j] = s.top();
else r[j] = -1;
s.push(j);
}
for(int j = 0; j < n; j++) if(l[j] != -1 && r[j] != -1) tot[l[j]][r[j]].push_back(i);
}
for(int i = 0; i < n; i++) {
for(int j = i+2; j < n; j++) {
if(!tot[i][j].size()) continue;
int prv = -1;
tot[i][j].erase(unique(tot[i][j].begin(), tot[i][j].end()), tot[i][j].end());
for(int k = 1; k < tot[i][j].size(); k++) {
if(tot[i][j][k]-tot[i][j][k-1] > 1) {
while(prv < k-1) {
goodh[tot[i][j][prv+1]][i+1].push_back({tot[i][j][k-1], j-1});
prv++;
}
}
}
while(prv < (int)tot[i][j].size()-1) {
goodh[tot[i][j][prv+1]][i+1].push_back({tot[i][j][tot[i][j].size()-1], j-1});
prv++;
}
tot[i][j].clear();
}
}
for(int i = 1; i < n-1; i++) {
stack<int> s;
int l[m], r[m];
for(int j = 0; j < m; j++) {
while(s.size() && a[s.top()][i] <= a[j][i]) s.pop();
if(s.size()) l[j] = s.top();
else l[j] = -1;
s.push(j);
}
while(s.size()) s.pop();
for(int j = m-1; j >= 0; j--) {
while(s.size() && a[s.top()][i] <= a[j][i]) s.pop();
if(s.size()) r[j] = s.top();
else r[j] = -1;
s.push(j);
}
for(int j = 0; j < m; j++) if(l[j] != -1 && r[j] != -1) tot[l[j]][r[j]].push_back(i);
}
for(int i = 0; i < m; i++) {
for(int j = i+2; j < m; j++) {
if(!tot[i][j].size()) continue;
int prv = -1;
tot[i][j].erase(unique(tot[i][j].begin(), tot[i][j].end()), tot[i][j].end());
for(int k = 1; k < tot[i][j].size(); k++) {
if(tot[i][j][k]-tot[i][j][k-1] > 1) {
while(prv < k-1) {
goodv[i+1][tot[i][j][prv+1]].push_back({j-1, tot[i][j][k-1]});
prv++;
}
}
}
while(prv < (int)tot[i][j].size()-1) {
goodv[i+1][tot[i][j][prv+1]].push_back({j-1, tot[i][j][tot[i][j].size()-1]});
prv++;
}
}
}
long long ans = 0;
for(int i = 1; i < m-1; i++) {
for(int j = 1; j < n-1; j++) {
sort(goodh[i][j].begin(), goodh[i][j].end());
sort(goodv[i][j].begin(), goodv[i][j].end());
int idx = 0;
for(auto k : goodh[i][j]) {
while(idx < goodv[i][j].size() && goodv[i][j][idx].first <= k.first) {
update(j, goodv[i][j][idx++].second, 1);
}
ans += query(k.second);
}
for(int k = 0; k < idx; k++) update(j, goodv[i][j][k].second, -1);
}
}
return ans;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:50:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int k = 1; k < tot[i][j].size(); k++) {
| ~~^~~~~~~~~~~~~~~~~~
rect.cpp:88:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int k = 1; k < tot[i][j].size(); k++) {
| ~~^~~~~~~~~~~~~~~~~~
rect.cpp:109:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | while(idx < goodv[i][j].size() && goodv[i][j][idx].first <= k.first) {
| ~~~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
444 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
756 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
444 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
756 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
2 ms |
1372 KB |
Output is correct |
23 |
Correct |
2 ms |
1236 KB |
Output is correct |
24 |
Correct |
2 ms |
1372 KB |
Output is correct |
25 |
Correct |
2 ms |
1116 KB |
Output is correct |
26 |
Correct |
2 ms |
1116 KB |
Output is correct |
27 |
Correct |
2 ms |
1116 KB |
Output is correct |
28 |
Correct |
2 ms |
1116 KB |
Output is correct |
29 |
Correct |
1 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
444 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
2 ms |
1372 KB |
Output is correct |
18 |
Correct |
2 ms |
1236 KB |
Output is correct |
19 |
Correct |
2 ms |
1372 KB |
Output is correct |
20 |
Correct |
2 ms |
1116 KB |
Output is correct |
21 |
Correct |
2 ms |
1116 KB |
Output is correct |
22 |
Correct |
2 ms |
1116 KB |
Output is correct |
23 |
Correct |
2 ms |
1116 KB |
Output is correct |
24 |
Correct |
1 ms |
860 KB |
Output is correct |
25 |
Correct |
0 ms |
756 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
344 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
10 ms |
6232 KB |
Output is correct |
31 |
Correct |
10 ms |
6344 KB |
Output is correct |
32 |
Correct |
11 ms |
6492 KB |
Output is correct |
33 |
Correct |
11 ms |
4700 KB |
Output is correct |
34 |
Correct |
13 ms |
5664 KB |
Output is correct |
35 |
Correct |
14 ms |
5724 KB |
Output is correct |
36 |
Correct |
13 ms |
5580 KB |
Output is correct |
37 |
Correct |
13 ms |
5468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
444 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
2 ms |
1372 KB |
Output is correct |
18 |
Correct |
2 ms |
1236 KB |
Output is correct |
19 |
Correct |
2 ms |
1372 KB |
Output is correct |
20 |
Correct |
2 ms |
1116 KB |
Output is correct |
21 |
Correct |
2 ms |
1116 KB |
Output is correct |
22 |
Correct |
2 ms |
1116 KB |
Output is correct |
23 |
Correct |
2 ms |
1116 KB |
Output is correct |
24 |
Correct |
1 ms |
860 KB |
Output is correct |
25 |
Correct |
10 ms |
6232 KB |
Output is correct |
26 |
Correct |
10 ms |
6344 KB |
Output is correct |
27 |
Correct |
11 ms |
6492 KB |
Output is correct |
28 |
Correct |
11 ms |
4700 KB |
Output is correct |
29 |
Correct |
13 ms |
5664 KB |
Output is correct |
30 |
Correct |
14 ms |
5724 KB |
Output is correct |
31 |
Correct |
13 ms |
5580 KB |
Output is correct |
32 |
Correct |
13 ms |
5468 KB |
Output is correct |
33 |
Correct |
0 ms |
756 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
344 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
103 ms |
63496 KB |
Output is correct |
39 |
Correct |
87 ms |
58772 KB |
Output is correct |
40 |
Correct |
105 ms |
58708 KB |
Output is correct |
41 |
Correct |
78 ms |
53944 KB |
Output is correct |
42 |
Correct |
143 ms |
73812 KB |
Output is correct |
43 |
Correct |
139 ms |
76624 KB |
Output is correct |
44 |
Correct |
132 ms |
74140 KB |
Output is correct |
45 |
Correct |
130 ms |
73012 KB |
Output is correct |
46 |
Correct |
99 ms |
48884 KB |
Output is correct |
47 |
Correct |
131 ms |
51776 KB |
Output is correct |
48 |
Correct |
195 ms |
61584 KB |
Output is correct |
49 |
Correct |
214 ms |
62824 KB |
Output is correct |
50 |
Correct |
100 ms |
38076 KB |
Output is correct |
51 |
Correct |
110 ms |
38024 KB |
Output is correct |
52 |
Correct |
180 ms |
60496 KB |
Output is correct |
53 |
Correct |
189 ms |
61284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
147808 KB |
Output is correct |
2 |
Correct |
81 ms |
106896 KB |
Output is correct |
3 |
Correct |
109 ms |
147536 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
124 ms |
147812 KB |
Output is correct |
6 |
Correct |
113 ms |
147784 KB |
Output is correct |
7 |
Correct |
112 ms |
147800 KB |
Output is correct |
8 |
Correct |
111 ms |
147792 KB |
Output is correct |
9 |
Correct |
113 ms |
147648 KB |
Output is correct |
10 |
Correct |
113 ms |
147108 KB |
Output is correct |
11 |
Correct |
124 ms |
147272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
756 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
728 ms |
344944 KB |
Output is correct |
8 |
Correct |
1538 ms |
611820 KB |
Output is correct |
9 |
Correct |
1544 ms |
614156 KB |
Output is correct |
10 |
Correct |
1478 ms |
614156 KB |
Output is correct |
11 |
Correct |
315 ms |
319568 KB |
Output is correct |
12 |
Correct |
544 ms |
474388 KB |
Output is correct |
13 |
Correct |
578 ms |
496268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
444 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
2 ms |
1372 KB |
Output is correct |
18 |
Correct |
2 ms |
1236 KB |
Output is correct |
19 |
Correct |
2 ms |
1372 KB |
Output is correct |
20 |
Correct |
2 ms |
1116 KB |
Output is correct |
21 |
Correct |
2 ms |
1116 KB |
Output is correct |
22 |
Correct |
2 ms |
1116 KB |
Output is correct |
23 |
Correct |
2 ms |
1116 KB |
Output is correct |
24 |
Correct |
1 ms |
860 KB |
Output is correct |
25 |
Correct |
10 ms |
6232 KB |
Output is correct |
26 |
Correct |
10 ms |
6344 KB |
Output is correct |
27 |
Correct |
11 ms |
6492 KB |
Output is correct |
28 |
Correct |
11 ms |
4700 KB |
Output is correct |
29 |
Correct |
13 ms |
5664 KB |
Output is correct |
30 |
Correct |
14 ms |
5724 KB |
Output is correct |
31 |
Correct |
13 ms |
5580 KB |
Output is correct |
32 |
Correct |
13 ms |
5468 KB |
Output is correct |
33 |
Correct |
103 ms |
63496 KB |
Output is correct |
34 |
Correct |
87 ms |
58772 KB |
Output is correct |
35 |
Correct |
105 ms |
58708 KB |
Output is correct |
36 |
Correct |
78 ms |
53944 KB |
Output is correct |
37 |
Correct |
143 ms |
73812 KB |
Output is correct |
38 |
Correct |
139 ms |
76624 KB |
Output is correct |
39 |
Correct |
132 ms |
74140 KB |
Output is correct |
40 |
Correct |
130 ms |
73012 KB |
Output is correct |
41 |
Correct |
99 ms |
48884 KB |
Output is correct |
42 |
Correct |
131 ms |
51776 KB |
Output is correct |
43 |
Correct |
195 ms |
61584 KB |
Output is correct |
44 |
Correct |
214 ms |
62824 KB |
Output is correct |
45 |
Correct |
100 ms |
38076 KB |
Output is correct |
46 |
Correct |
110 ms |
38024 KB |
Output is correct |
47 |
Correct |
180 ms |
60496 KB |
Output is correct |
48 |
Correct |
189 ms |
61284 KB |
Output is correct |
49 |
Correct |
112 ms |
147808 KB |
Output is correct |
50 |
Correct |
81 ms |
106896 KB |
Output is correct |
51 |
Correct |
109 ms |
147536 KB |
Output is correct |
52 |
Correct |
1 ms |
348 KB |
Output is correct |
53 |
Correct |
124 ms |
147812 KB |
Output is correct |
54 |
Correct |
113 ms |
147784 KB |
Output is correct |
55 |
Correct |
112 ms |
147800 KB |
Output is correct |
56 |
Correct |
111 ms |
147792 KB |
Output is correct |
57 |
Correct |
113 ms |
147648 KB |
Output is correct |
58 |
Correct |
113 ms |
147108 KB |
Output is correct |
59 |
Correct |
124 ms |
147272 KB |
Output is correct |
60 |
Correct |
1 ms |
344 KB |
Output is correct |
61 |
Correct |
728 ms |
344944 KB |
Output is correct |
62 |
Correct |
1538 ms |
611820 KB |
Output is correct |
63 |
Correct |
1544 ms |
614156 KB |
Output is correct |
64 |
Correct |
1478 ms |
614156 KB |
Output is correct |
65 |
Correct |
315 ms |
319568 KB |
Output is correct |
66 |
Correct |
544 ms |
474388 KB |
Output is correct |
67 |
Correct |
578 ms |
496268 KB |
Output is correct |
68 |
Correct |
0 ms |
756 KB |
Output is correct |
69 |
Correct |
0 ms |
348 KB |
Output is correct |
70 |
Correct |
0 ms |
344 KB |
Output is correct |
71 |
Correct |
0 ms |
348 KB |
Output is correct |
72 |
Correct |
1 ms |
348 KB |
Output is correct |
73 |
Correct |
2011 ms |
809128 KB |
Output is correct |
74 |
Correct |
1265 ms |
716092 KB |
Output is correct |
75 |
Correct |
1969 ms |
716184 KB |
Output is correct |
76 |
Correct |
1095 ms |
649160 KB |
Output is correct |
77 |
Correct |
2644 ms |
965884 KB |
Output is correct |
78 |
Correct |
1876 ms |
537948 KB |
Output is correct |
79 |
Correct |
1921 ms |
568352 KB |
Output is correct |
80 |
Correct |
3050 ms |
785160 KB |
Output is correct |
81 |
Correct |
1855 ms |
554920 KB |
Output is correct |
82 |
Correct |
2502 ms |
685800 KB |
Output is correct |
83 |
Correct |
3097 ms |
813780 KB |
Output is correct |
84 |
Correct |
1649 ms |
535348 KB |
Output is correct |
85 |
Correct |
2857 ms |
798660 KB |
Output is correct |
86 |
Correct |
2793 ms |
780336 KB |
Output is correct |
87 |
Correct |
1336 ms |
658264 KB |
Output is correct |
88 |
Correct |
2789 ms |
965076 KB |
Output is correct |
89 |
Correct |
2575 ms |
965876 KB |
Output is correct |
90 |
Correct |
2601 ms |
965820 KB |
Output is correct |