#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void build(int tree[], int a[], int v, int l, int r) {
if(l == r) {
tree[v] = a[l];
}else{
int m = (l+r)/2;
build(tree, a, 2*v, l, m);
build(tree, a, 2*v+1, m+1, r);
tree[v] = max(tree[2*v], tree[2*v+1]);
}
}
int query(int tree[], int a[], int tl, int tr, int v, int l, int r) {
if(tr < tl || r < l) {
return 0;
}else if(tr == r && tl == l) {
return tree[v];
}else{
int m = (l+r)/2;
return max(
query(tree, a, tl, min(tr, m), 2*v, l, m), query(tree, a, max(tl, m+1), tr, 2*v+1, m+1, r)
);
}
}
long long count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
if(n <=2 || m<=2) {
return 0;
}else if(n == 3) {
int good[m+1];
for(int i=1;i<=m-2;i++) {
good[i] = (a[1][i] < a[0][i] && a[1][i] < a[2][i]);
}
vector<pair<int, int>> vec;
int arr[m];
int tree[4*m];
for(int i=1;i<=m-2;i++) {
arr[i-1] = a[1][i];
}
for(int i=1;i<=m-2;i++) {
if(good[i]) {
vec.push_back({i, i});
i++;
while(i<=m-2 && good[i]) {
vec[vec.size()-1].second++;
i++;
}
i--;
}
}
build(tree, arr, 1, 0, m-3);
int ans = 0;
for(int k=0;k<vec.size();k++) {
int s = vec[k].first;
int e = vec[k].second;
for(int i=s;i<=e;i++) {
for(int j=i;j<=e;j++) {
int ma = query(tree, arr, i-1, j-1, 1, 0, m-3);
if(ma < a[1][i-1] && ma < a[1][j+1]) {
ans++;
}
}
}
}
return ans;
}
return 0;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int k=0;k<vec.size();k++) {
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
444 ms |
604 KB |
Output is correct |
2 |
Correct |
307 ms |
564 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |