Submission #867712

#	Time	Username	Problem	Language	Result	Execution time	Memory
867712		JakobZorz	Rectangles (IOI19_rect)	C++17	72 / 100	5055 ms	762052 KiB

rect

#include"rect.h"
#include<algorithm>
#include<unordered_set>
#include<set>
#include<iostream>
using namespace std;
typedef long long ll;
 
int gap_up[2500][2500];
short gap_up_max[2500][2500][12];
int gap_down[2500][2500];
short gap_down_min[2500][2500][12];
int gap_left[2500][2500];
short gap_left_max[2500][2500][12];
int gap_right[2500][2500];
short gap_right_min[2500][2500][12];
int arr[2500][2500];
int highest_pow2[2501];
int w,h;

void setup(){
    for(int i=1;i<2501;i++){
        int pow2=0;
        while((1<<pow2)<=i)
            pow2++;
        highest_pow2[i]=pow2-1;
    }
    
    for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){
            gap_down_min[x][y][0]=x;
        }
        
        for(int p=1;p<12;p++){
            for(int x=0;x<w-(1<<(p-1));x++){
                int val1=gap_down[gap_down_min[x][y][p-1]][y];
                int val2=gap_down[gap_down_min[x+(1<<(p-1))][y][p-1]][y];
                if(val1<val2){
                    gap_down_min[x][y][p]=gap_down_min[x][y][p-1];
                }else{
                    gap_down_min[x][y][p]=gap_down_min[x+(1<<(p-1))][y][p-1];
                }
            }
        }
    }
    
    for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){
            gap_up_max[x][y][0]=x;
        }
        
        for(int p=1;p<12;p++){
            for(int x=0;x<w-(1<<(p-1));x++){
                int val1=gap_up[gap_up_max[x][y][p-1]][y];
                int val2=gap_up[gap_up_max[x+(1<<(p-1))][y][p-1]][y];
                if(val1>val2){
                    gap_up_max[x][y][p]=gap_up_max[x][y][p-1];
                }else{
                    gap_up_max[x][y][p]=gap_up_max[x+(1<<(p-1))][y][p-1];
                }
            }
        }
    }
    
    for(int x=0;x<w;x++){
        for(int y=0;y<h;y++){
            gap_right_min[x][y][0]=y;
        }
        
        for(int p=1;p<12;p++){
            for(int y=0;y<h-(1<<(p-1));y++){
                int val1=gap_right[x][gap_right_min[x][y][p-1]];
                int val2=gap_right[x][gap_right_min[x][y+(1<<(p-1))][p-1]];
                if(val1<val2){
                    gap_right_min[x][y][p]=gap_right_min[x][y][p-1];
                }else{
                    gap_right_min[x][y][p]=gap_right_min[x][y+(1<<(p-1))][p-1];
                }
            }
        }
    }
    
    for(int x=0;x<w;x++){
        for(int y=0;y<h;y++){
            gap_left_max[x][y][0]=y;
        }
        
        for(int p=1;p<12;p++){
            for(int y=0;y<h-(1<<(p-1));y++){
                int val1=gap_left[x][gap_left_max[x][y][p-1]];
                int val2=gap_left[x][gap_left_max[x][y+(1<<(p-1))][p-1]];
                if(val1>val2){
                    gap_left_max[x][y][p]=gap_left_max[x][y][p-1];
                }else{
                    gap_left_max[x][y][p]=gap_left_max[x][y+(1<<(p-1))][p-1];
                }
            }
        }
    }
}

int get_min_down(int y,int x1,int x2){
    if(x1==x2)
        return 2500;
    int pow2=highest_pow2[x2-x1];
    return min(gap_down[gap_down_min[x1][y][pow2]][y],gap_down[gap_down_min[x2-(1<<pow2)][y][pow2]][y]);
}

int get_max_up(int y,int x1,int x2){
    if(x1==x2)
        return -1;
    int pow2=highest_pow2[x2-x1];
    return max(gap_up[gap_up_max[x1][y][pow2]][y],gap_up[gap_up_max[x2-(1<<pow2)][y][pow2]][y]);
}

int get_min_right(int x,int y1,int y2){
    if(y1==y2)
        return 2500;
    int pow2=highest_pow2[y2-y1];
    return min(gap_right[x][gap_right_min[x][y1][pow2]],gap_right[x][gap_right_min[x][y2-(1<<pow2)][pow2]]);
}

int get_max_left(int x,int y1,int y2){
    if(y1==y2)
        return 2500;
    int pow2=highest_pow2[y2-y1];
    return max(gap_left[x][gap_left_max[x][y1][pow2]],gap_left[x][gap_left_max[x][y2-(1<<pow2)][pow2]]);
}

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)
            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);
    
    setup();
    
    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