#include<bits/stdc++.h>
#include "rect.h"
using namespace std;
long long count_rectangles(vector<vector<int> > a) {
int N = a[0].size();
vector<int> bad(N,0);
for(int i = 1;i < N-1;i++){
if(a[1][i] < a[0][i] && a[1][i] < a[2][i]){
bad[i] = false;
}else{
bad[i] = true;
}
}
for(int i = 1;i < N;i++){
bad[i] += bad[i-1];
}
// sparse table;
// int k = __lg(N)+1;
// vector<vector<int>> spt(k,vector<int>(N));
// spt[0] = a[1];
// for(int layer = 1;layer < k;layer++){
// for(int s = 0;s+(1 << layer)-1 < N;s++){
// spt[layer][s] = max(spt[layer-1][s],spt[layer-1][s+(1 << (layer-1))]);
// }
// }
// auto ask = [&](int l,int r){
// int len = r-l+1;
// int layer = __lg(len);
// return max(spt[layer][l],spt[layer][r-(1 << layer)+1]);
// };
long long ans = 0;
for(int l = 0;l < N;l++){
int cmax = a[1][l+1];
for(int r = l+2;r < N;r++){
// int midmax = ask(l+1,r-1);
int midmax = cmax;
// cout << "(" << l << "," << r << "):" << midmax << "," << bad[r-1]-bad[l] << endl;
if(midmax < a[1][l] && midmax < a[1][r] && bad[r-1]-bad[l] == 0){
ans++;
}
cmax = max(cmax,a[1][r]);
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |