이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <array>
using namespace std;
typedef long long ll;
const int maxn=2505, Log=12, pot=(1<<Log);
const int inf=1e9;
struct tmin{
int t[pot*2];
tmin(){
for(int i=0; i<pot*2; i++){
t[i]=inf;
}
}
void update(int x, int val){
t[x]=val;
for(x/=2; x>0; x/=2){
t[x]=min(t[x*2], t[x*2+1]);
}
}
int query(int L, int D, int x, int l, int d){
if(L>=l && D<=d){
return t[x];
}
int lijeva=inf, desna=inf;
if((L+D)/2>=l){
lijeva=query(L, (L+D)/2, x*2, l, d);
}
if((L+D)/2+1<=d){
desna=query((L+D)/2+1, D, x*2+1, l, d);
}
return min(lijeva, desna);
}
};
struct tmax{
int t[pot*2];
void update(int x, int val){
t[x]=val;
for(x/=2; x>0; x/=2){
t[x]=max(t[x*2], t[x*2+1]);
}
}
int query(int L, int D, int x, int l, int d){
if(L>=l && D<=d){
return t[x];
}
int lijeva=0, desna=0;
if((L+D)/2>=l){
lijeva=query(L, (L+D)/2, x*2, l, d);
}
if((L+D)/2+1<=d){
desna=query((L+D)/2+1, D, x*2+1, l, d);
}
return max(lijeva, desna);
}
};
tmin R1[maxn], C1[maxn];
tmax R2[maxn], C2[maxn];
ll sol;
array < int, 4 > svi[maxn][maxn];
int n, m;
map < array < int, 4 >, bool > bio;
ll count_rectangles(vector < vector < int > > a){
n=a.size();
m=a[0].size();
vector < pair <int, int > > v;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][2]=0;
}
else{
svi[i][j][2]=v.back().second+1;
}
v.push_back({a[i][j], j});
}
v.clear();
for(int j=m-1; j>-1; j--){
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][3]=m-1;
}
else{
svi[i][j][3]=v.back().second-1;
}
v.push_back({a[i][j], j});
}
v.clear();
}
for(int j=0; j<m; j++){
for(int i=0; i<n; i++){
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][0]=0;
}
else{
svi[i][j][0]=v.back().second+1;
}
v.push_back({a[i][j], i});
}
v.clear();
for(int i=n-1; i>-1; i--){
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][1]=n-1;
}
else{
svi[i][j][1]=v.back().second-1;
}
v.push_back({a[i][j], i});
}
v.clear();
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
R1[i].update(j+pot, svi[i][j][0]);
R2[i].update(j+pot, svi[i][j][1]);
C1[j].update(i+pot, svi[i][j][2]);
C2[j].update(i+pot, svi[i][j][3]);
}
}
array < int, 4 > c;
// array < int, 4 > b;
for(int i=1; i<n-1; i++){
for(int j=1; j<m-1; j++){
c=svi[i][j];
if(c[0]==0 || c[2]==0 || c[1]==n-1 || c[3]==m-1 || bio[c]){
continue;
}
/* if(i==1 && j==1){
cout << R1[c[1]+1].query(0, pot-1, 1, c[2], c[3]) << endl;
}*/
if(c[0]<R1[c[1]+1].query(0, pot-1, 1, c[2], c[3])){
continue;
}
if(c[1]>R2[c[0]-1].query(0, pot-1, 1, c[2], c[3])){
continue;
}
if(c[2]<C1[c[3]+1].query(0, pot-1, 1, c[0], c[1])){
continue;
}
if(c[3]>C2[c[2]-1].query(0, pot-1, 1, c[0], c[1])){
continue;
}
bio[c]=1;
sol++;
}
}
return sol;
}
# | 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... |