#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>stosy[2510];
int nast[2510][2510][4];
int nast2[2510][2510][4];
const int base = 1<<12;
int tree1[2510][2*base];
int tree2[2510][2*base];
int tree3[2*base][2510];
int tree4[2*base][2510];
int MAXI1(int w, int l, int p, int a, int b, int war){
if(p<a || b<l)return -1;
if(a<=l && p<=b)return tree3[w][war];
return max(MAXI1(w*2, l, (l+p)/2, a, b, war), MAXI1(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MINI1(int w, int l, int p, int a, int b, int war){
if(p<a || b<l)return 2600;
if(a<=l && p<=b)return tree4[w][war];
return min(MINI1(w*2, l, (l+p)/2, a, b, war), MINI1(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MAXI2(int w, int l, int p, int a, int b, int war){
if(p<a || b<l)return -1;
if(a<=l && p<=b)return tree1[war][w];
return max(MAXI2(w*2, l, (l+p)/2, a, b, war), MAXI2(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MINI2(int w, int l, int p, int a, int b, int war){
if(p<a || b<l)return 2600;
if(a<=l && p<=b)return tree2[war][w];
return min(MINI2(w*2, l, (l+p)/2, a, b, war), MINI2(w*2+1, (l+p)/2+1, p, a, b, war));
}
int maxi1(int war, int l, int r){
// printf("%d %d %d ", war, l, r);
l+=base, r+=base;
if(l>r)return -1;
int res = max(tree3[l][war], tree3[r][war]);
while(l/2<r/2){
if((l&1)==0){
res = max(res, tree3[l^1][war]);
}
if(r&1){
res = max(res, tree3[r^1][war]);
}
l>>=1;
r>>=1;
}
// printf("%d\n", res);
return res;
return MAXI1(1, 0, base-1, l, r, war);
for(int i=l;i<=r;i++)
res = max(res, nast2[i][war][0]);
return res;
}
int mini1(int war, int l, int r){
l+=base, r+=base;
if(l>r)return 2600;
int res = min(tree4[l][war], tree4[r][war]);
while(l/2<r/2){
if((l&1)==0){
res = min(res, tree4[l^1][war]);
}
if(r&1){
res = min(res, tree4[r^1][war]);
}
l>>=1;
r>>=1;
}
// printf("%d\n", res);
return res;
return MINI1(1, 0, base-1, l, r, war);
int res = 2600;
for(int i=l;i<=r;i++)
res = min(res, nast2[i][war][1]);
return res;
}
int maxi2(int war, int l, int r){
return MAXI2(1, 0, base-1, l, r, war);
int res = -1;
for(int i=l;i<=r;i++)
res = max(res, nast2[war][i][2]);
return res;
}
int mini2(int war, int l, int r){
return MINI2(1, 0, base-1, l, r, war);
int res = 2600;
for(int i=l;i<=r;i++)
res = min(res, nast2[war][i][3]);
return res;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size();
int m = a[0].size();
int i, j;
//poprzednie po x [0]
for(i=0;i<n;i++){
for(j=0;j<m;j++){
while(stosy[i].size() && stosy[i].back().first<=a[i][j])
stosy[i].pop_back();
if(stosy[i].size())
nast[i][j][0] = stosy[i].back().second;
else
nast[i][j][0] = -1;
stosy[i].push_back({a[i][j], j});
}
}
for(i=0;i<n;i++)
stosy[i].clear();
//nastepne po x [1]
for(i=0;i<n;i++){
for(j=m-1;j>=0;j--){
while(stosy[i].size() && stosy[i].back().first<=a[i][j])
stosy[i].pop_back();
if(stosy[i].size())
nast[i][j][1] = stosy[i].back().second;
else
nast[i][j][1] = m;
stosy[i].push_back({a[i][j], j});
}
}
for(i=0;i<n;i++)
stosy[i].clear();
//poprzednie po y [2]
for(i=0;i<m;i++){
for(j=0;j<n;j++){
while(stosy[i].size() && stosy[i].back().first<=a[j][i])
stosy[i].pop_back();
if(stosy[i].size())
nast[j][i][2] = stosy[i].back().second;
else
nast[j][i][2] = -1;
stosy[i].push_back({a[j][i], j});
}
}
for(i=0;i<m;i++)
stosy[i].clear();
//nastepne po y [3]
for(i=0;i<m;i++){
for(j = n-1;j>=0;j--){
while(stosy[i].size() && stosy[i].back().first<=a[j][i])
stosy[i].pop_back();
if(stosy[i].size())
nast[j][i][3] = stosy[i].back().second;
else
nast[j][i][3] = n;
stosy[i].push_back({a[j][i], j});
}
}
for(i=0;i<m;i++)
stosy[i].clear();
for(i=0;i<n;i++){
for(j=0;j<m;j++){
while(stosy[i].size() && stosy[i].back().first<a[i][j])
stosy[i].pop_back();
if(stosy[i].size())
nast2[i][j][0] = stosy[i].back().second;
else
nast2[i][j][0] = -1;
stosy[i].push_back({a[i][j], j});
}
}
for(i=0;i<n;i++)
stosy[i].clear();
//nastepne po x [1]
for(i=0;i<n;i++){
for(j=m-1;j>=0;j--){
while(stosy[i].size() && stosy[i].back().first<a[i][j])
stosy[i].pop_back();
if(stosy[i].size())
nast2[i][j][1] = stosy[i].back().second;
else
nast2[i][j][1] = m;
stosy[i].push_back({a[i][j], j});
}
}
for(i=0;i<n;i++)
stosy[i].clear();
//poprzednie po y [2]
for(i=0;i<m;i++){
for(j=0;j<n;j++){
while(stosy[i].size() && stosy[i].back().first<a[j][i])
stosy[i].pop_back();
if(stosy[i].size())
nast2[j][i][2] = stosy[i].back().second;
else
nast2[j][i][2] = -1;
stosy[i].push_back({a[j][i], j});
}
}
for(i=0;i<m;i++)
stosy[i].clear();
//nastepne po y [3]
for(i=0;i<m;i++){
for(j = n-1;j>=0;j--){
while(stosy[i].size() && stosy[i].back().first<a[j][i])
stosy[i].pop_back();
if(stosy[i].size())
nast2[j][i][3] = stosy[i].back().second;
else
nast2[j][i][3] = n;
stosy[i].push_back({a[j][i], j});
}
}
for(i=0;i<m;i++)
stosy[i].clear();
vector<pair<pair<int,int>, pair<int,int>>>sett;
for(i=1;i<n-1;i++)
for(j=1;j<m-1;j++){
//printf("%d %d %d %d\n", nast[i][j][0], nast[i][j][1], nast[i][j][2], nast[i][j][3]);
if(nast[i][j][0]!=-1 && nast[i][j][1]!=m && nast[i][j][2]!=-1 && nast[i][j][3]!=n){
//printf("dodaje\n");
sett.push_back({{nast[i][j][0], nast[i][j][1]}, {nast[i][j][2], nast[i][j][3]}});
}
}
for(i=0;i<n;i++)
for(j=0;j<m;j++){
tree3[base+i][j] = nast2[i][j][0];
tree4[base+i][j] = nast2[i][j][1];
tree1[i][base+j] = nast2[i][j][2];
tree2[i][base+j] = nast2[i][j][3];
}
for(i=0;i<n;i++)
for(j=base-1;j>0;j--){
tree1[i][j] = max(tree1[i][j*2], tree1[i][j*2+1]);
tree2[i][j] = min(tree2[i][j*2], tree2[i][j*2+1]);
}
for(i=0;i<m;i++)
for(j=base-1;j>0;j--){
tree3[j][i] = max(tree3[j*2][i], tree3[j*2+1][i]);
tree4[j][i] = min(tree4[j*2][i], tree4[j*2+1][i]);
}
sort(sett.begin(), sett.end());
long long wynik = 0;
for(i=0;i<(int)sett.size();i++){
if(i!=0 && sett[i-1]==sett[i])continue;
auto x = sett[i];
if(mini1(x.first.first, x.second.first+1, x.second.second-1)<x.first.second)continue;
if(maxi1(x.first.second, x.second.first+1, x.second.second-1)>x.first.first)continue;
if(mini2(x.second.first, x.first.first+1, x.first.second-1)<x.second.second)continue;
if(maxi2(x.second.second, x.first.first+1, x.first.second-1)>x.second.first)continue;
wynik++;
}
return wynik;
}
Compilation message
rect.cpp: In function 'int mini1(int, int, int)':
rect.cpp:75:6: error: redeclaration of 'int res'
75 | int res = 2600;
| ^~~
rect.cpp:60:6: note: 'int res' previously declared here
60 | int res = min(tree4[l][war], tree4[r][war]);
| ^~~
