이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#include "rect.h"
//#include"grader.cpp"
int n,m;
int nxt[2505][2505],prv[2505][2505];
long long count_rectangles(vector<vector<int>>a) {
n=a.size();
m=a[0].size();
if(n<3||m<3)return 0;
vector<vector<pair<int,int>>>v(n);
for(int i=1;i<n-1;i++){
vector<int>pos;
for(int j=m-1;j>=0;j--){
while(!pos.empty()&&a[i][pos.back()]<=a[i][j]){
v[i].push_back({j,pos.back()});
pos.pop_back();
}
if(!pos.empty())v[i].push_back({j,pos.back()});
nxt[i][j]=(pos.empty()?m:pos.back());
pos.push_back(j);
}
pos.clear();
for(int j=0;j<m;j++){
while(!pos.empty()&&a[i][pos.back()]<=a[i][j])pos.pop_back();
prv[i][j]=(pos.empty()?-1:pos.back());
pos.push_back(j);
}
}
long long res=0;
for(int i=1;i<n-1;i++){
for(auto[st,en]:v[i]){
if(en-st==1){
continue;
}
int mx[en-st+5]={};
for(int dep=0;i+dep<n-1;dep++){
if(nxt[i+dep][st]<en||prv[i+dep][en]>st){
break;
}
int cnt=0,flag=1;
for(int j=st+1;j<en&&flag;j++){
mx[j-st]=max(mx[j-st],a[i+dep][j]);
if(a[i+dep][j]>a[i-1][j])flag=0;
}
if(!flag){
break;
}
for(int j=st+1;j<en;j++)cnt+=mx[j-st]>a[i+dep+1][j];
if(cnt==0)res++;
}
}
}
return res;
}
# | 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... |