Submission #867610

#	Time	Username	Problem	Language	Result	Execution time	Memory
867610		JakobZorz	Rectangles (IOI19_rect)	C++17	72 / 100	5026 ms	171944 KiB

rect

#include"rect.h"
#include<algorithm>
#include<unordered_set>
#include<set>
#include<iostream>
using namespace std;
typedef long long ll;
 
int gap_right[2500][2500];
int gap_down[2500][2500];
int gap_left[2500][2500];
int gap_up[2500][2500];
int arr[2500][2500];
int w,h;
 
int get_min_down(int y,int x1,int x2){
    int res=2500;
    for(int x=x1;x<x2;x++)
        res=min(res,gap_down[x][y]);
    return res;
}
 
int get_max_up(int y,int x1,int x2){
    int res=-1;
    for(int x=x1;x<x2;x++)
        res=max(res,gap_up[x][y]);
    return res;
}
 
int get_min_right(int x,int y1,int y2){
    int res=2500;
    for(int y=y1;y<y2;y++)
        res=min(res,gap_right[x][y]);
    return res;
}
 
int get_max_left(int x,int y1,int y2){
    int res=-1;
    for(int y=y1;y<y2;y++)
        res=max(res,gap_left[x][y]);
    return res;
}

void process_column(int x){
    vector<pair<int,int>>vals;
    for(int y=0;y<h;y++){
        while(!vals.empty()&&vals.back().first<arr[x][y])
            vals.pop_back();
        gap_up[x][y]=-1;
        if(!vals.empty())
            gap_up[x][y]=vals.back().second;
        vals.emplace_back(arr[x][y],y);
    }
    
    vals.clear();
    for(int y=h-1;y>=0;y--){
        while(!vals.empty()&&vals.back().first<arr[x][y])
            vals.pop_back();
        gap_down[x][y]=2500;
        if(!vals.empty())
            gap_down[x][y]=vals.back().second;
        vals.emplace_back(arr[x][y],y);
    }
}
 
void process_row(int y){
    vector<pair<int,int>>vals;
    for(int x=0;x<w;x++){
        while(!vals.empty()&&vals.back().first<arr[x][y])
            vals.pop_back();
        gap_left[x][y]=-1;
        if(!vals.empty())
            gap_left[x][y]=vals.back().second;
        vals.emplace_back(arr[x][y],x);
    }
    
    vals.clear();
    for(int x=w;x>=0;x--){
        while(!vals.empty()&&vals.back().first<arr[x][y])
            vals.pop_back();
        gap_right[x][y]=2500;
        if(!vals.empty())
            gap_right[x][y]=vals.back().second;
        vals.emplace_back(arr[x][y],x);
    }
}
 
int check1(int x1,int x2,int y){
    if(x1==-1||x2==2500||x1==x2-1)
        return 0;
    
    int y1=y-1;
    
    int y2=get_min_down(y1,x1+1,x2);
    
    if(y2>=h)
        return 0;
    
    if(y1==y2-1)
        return 0;
    
    if(get_max_up(y2,x1+1,x2)>y1)
        return 0;
    
    if(get_min_right(x1,y1+1,y2)<x2)
        return 0;
    
    if(get_max_left(x2,y1+1,y2)>x1)
        return 0;
    
    for(int x=x1+1;x<x2;x++)
        if(gap_down[x][y1]!=y2&&gap_up[x][y2]!=y1)
            return 0;
    
    for(int y=y1+1;y<y2;y++)
        if(gap_right[x1][y]!=x2&&gap_left[x2][y]!=x1)
            return 0;
    
    return 1;
}
 
int check2(int x1,int x2,int y){
    if(x1==-1||x2==2500||x1==x2-1)
        return 0;
    
    int y2=y+1;
    
    int y1=get_max_up(y2,x1+1,x2);
    
    if(y1==-1)
        return 0;
    
    if(y1==y2-1)
        return 0;
    
    if(get_min_down(y1,x1+1,x2)<y2)
        return 0;
    
    if(get_min_right(x1,y1+1,y2)<x2)
        return 0;
    
    if(get_max_left(x2,y1+1,y2)>x1)
        return 0;
    
    for(int x=x1+1;x<x2;x++)
        if((gap_down[x][y1]!=y2&&gap_up[x][y2]!=y1)||gap_down[x][y1]==y2)
            return 0;
    
    for(int y=y1+1;y<y2;y++)
        if(gap_right[x1][y]!=x2&&gap_left[x2][y]!=x1)
            return 0;
    
    return 1;
}
 
int check(int x1,int x2,int y){
    return check1(x1,x2,y)+check2(x1,x2,y);
}
 
ll count_rectangles(vector<vector<int>>a_){
    h=(int)a_.size();
    w=(int)a_[0].size();
    for(int x=0;x<w;x++){
        for(int y=0;y<h;y++){
            arr[x][y]=a_[y][x];
        }
    }
    
    for(int x=0;x<w;x++)
        process_column(x);
    
    for(int y=0;y<h;y++)
        process_row(y);
    
    ll res=0;
    for(int x=0;x<w;x++)
        for(int y=1;y<h-1;y++){
            res+=check(x,gap_right[x][y],y);
            if(arr[gap_left[x][y]][y]!=arr[x][y])
                res+=check(gap_left[x][y],x,y);
        }
    
    return res;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28