oj.uz

Submission #867712

# Submission time Handle Problem Language Result Execution time Memory
867712 2023-10-29T09:52:00 Z JakobZorz Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 762052 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 2 ms 20828 KB Output is correct
8 Correct 4 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct
11 Correct 3 ms 26972 KB Output is correct
12 Correct 3 ms 27164 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 18776 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16732 KB Output is correct
18 Correct 2 ms 16880 KB Output is correct
19 Correct 4 ms 26972 KB Output is correct
20 Correct 3 ms 20828 KB Output is correct
21 Correct 2 ms 16860 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 2 ms 20828 KB Output is correct
8 Correct 4 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct
11 Correct 3 ms 26972 KB Output is correct
12 Correct 3 ms 27164 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 18776 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16732 KB Output is correct
18 Correct 2 ms 16880 KB Output is correct
19 Correct 4 ms 26972 KB Output is correct
20 Correct 3 ms 20828 KB Output is correct
21 Correct 2 ms 16860 KB Output is correct
22 Correct 5 ms 41564 KB Output is correct
23 Correct 6 ms 41564 KB Output is correct
24 Correct 5 ms 41564 KB Output is correct
25 Correct 6 ms 41564 KB Output is correct
26 Correct 5 ms 41564 KB Output is correct
27 Correct 5 ms 41564 KB Output is correct
28 Correct 6 ms 41564 KB Output is correct
29 Correct 4 ms 29276 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 2 ms 20828 KB Output is correct
8 Correct 4 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct
11 Correct 3 ms 26972 KB Output is correct
12 Correct 3 ms 27164 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 18776 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 5 ms 41564 KB Output is correct
18 Correct 6 ms 41564 KB Output is correct
19 Correct 5 ms 41564 KB Output is correct
20 Correct 6 ms 41564 KB Output is correct
21 Correct 5 ms 41564 KB Output is correct
22 Correct 5 ms 41564 KB Output is correct
23 Correct 6 ms 41564 KB Output is correct
24 Correct 4 ms 29276 KB Output is correct
25 Correct 2 ms 16732 KB Output is correct
26 Correct 2 ms 16880 KB Output is correct
27 Correct 4 ms 26972 KB Output is correct
28 Correct 3 ms 20828 KB Output is correct
29 Correct 2 ms 16860 KB Output is correct
30 Correct 18 ms 72796 KB Output is correct
31 Correct 18 ms 72948 KB Output is correct
32 Correct 19 ms 72956 KB Output is correct
33 Correct 12 ms 72540 KB Output is correct
34 Correct 14 ms 72792 KB Output is correct
35 Correct 15 ms 72872 KB Output is correct
36 Correct 14 ms 72900 KB Output is correct
37 Correct 14 ms 72784 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 2 ms 20828 KB Output is correct
8 Correct 4 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct
11 Correct 3 ms 26972 KB Output is correct
12 Correct 3 ms 27164 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 18776 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 5 ms 41564 KB Output is correct
18 Correct 6 ms 41564 KB Output is correct
19 Correct 5 ms 41564 KB Output is correct
20 Correct 6 ms 41564 KB Output is correct
21 Correct 5 ms 41564 KB Output is correct
22 Correct 5 ms 41564 KB Output is correct
23 Correct 6 ms 41564 KB Output is correct
24 Correct 4 ms 29276 KB Output is correct
25 Correct 18 ms 72796 KB Output is correct
26 Correct 18 ms 72948 KB Output is correct
27 Correct 19 ms 72956 KB Output is correct
28 Correct 12 ms 72540 KB Output is correct
29 Correct 14 ms 72792 KB Output is correct
30 Correct 15 ms 72872 KB Output is correct
31 Correct 14 ms 72900 KB Output is correct
32 Correct 14 ms 72784 KB Output is correct
33 Correct 2 ms 16732 KB Output is correct
34 Correct 2 ms 16880 KB Output is correct
35 Correct 4 ms 26972 KB Output is correct
36 Correct 3 ms 20828 KB Output is correct
37 Correct 2 ms 16860 KB Output is correct
38 Correct 79 ms 223972 KB Output is correct
39 Correct 76 ms 224064 KB Output is correct
40 Correct 79 ms 224000 KB Output is correct
41 Correct 78 ms 223944 KB Output is correct
42 Correct 327 ms 224176 KB Output is correct
43 Correct 368 ms 224128 KB Output is correct
44 Correct 320 ms 224824 KB Output is correct
45 Correct 297 ms 223744 KB Output is correct
46 Correct 83 ms 222648 KB Output is correct
47 Correct 96 ms 222540 KB Output is correct
48 Correct 120 ms 223060 KB Output is correct
49 Correct 125 ms 224500 KB Output is correct
50 Correct 71 ms 120636 KB Output is correct
51 Correct 72 ms 221316 KB Output is correct
52 Correct 118 ms 223828 KB Output is correct
53 Correct 123 ms 224432 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 668916 KB Output is correct
2 Correct 63 ms 618296 KB Output is correct
3 Correct 64 ms 669012 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 67 ms 669012 KB Output is correct
6 Correct 66 ms 668964 KB Output is correct
7 Correct 66 ms 670932 KB Output is correct
8 Correct 65 ms 668852 KB Output is correct
9 Correct 67 ms 670808 KB Output is correct
10 Correct 64 ms 668752 KB Output is correct
11 Correct 66 ms 668896 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16880 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 2 ms 16860 KB Output is correct
6 Correct 2 ms 18936 KB Output is correct
7 Correct 465 ms 696660 KB Output is correct
8 Correct 956 ms 762052 KB Output is correct
9 Correct 949 ms 759120 KB Output is correct
10 Correct 962 ms 758960 KB Output is correct
11 Correct 373 ms 713232 KB Output is correct
12 Correct 675 ms 724700 KB Output is correct
13 Correct 738 ms 759120 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 2 ms 20828 KB Output is correct
8 Correct 4 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct
11 Correct 3 ms 26972 KB Output is correct
12 Correct 3 ms 27164 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 18776 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 5 ms 41564 KB Output is correct
18 Correct 6 ms 41564 KB Output is correct
19 Correct 5 ms 41564 KB Output is correct
20 Correct 6 ms 41564 KB Output is correct
21 Correct 5 ms 41564 KB Output is correct
22 Correct 5 ms 41564 KB Output is correct
23 Correct 6 ms 41564 KB Output is correct
24 Correct 4 ms 29276 KB Output is correct
25 Correct 18 ms 72796 KB Output is correct
26 Correct 18 ms 72948 KB Output is correct
27 Correct 19 ms 72956 KB Output is correct
28 Correct 12 ms 72540 KB Output is correct
29 Correct 14 ms 72792 KB Output is correct
30 Correct 15 ms 72872 KB Output is correct
31 Correct 14 ms 72900 KB Output is correct
32 Correct 14 ms 72784 KB Output is correct
33 Correct 79 ms 223972 KB Output is correct
34 Correct 76 ms 224064 KB Output is correct
35 Correct 79 ms 224000 KB Output is correct
36 Correct 78 ms 223944 KB Output is correct
37 Correct 327 ms 224176 KB Output is correct
38 Correct 368 ms 224128 KB Output is correct
39 Correct 320 ms 224824 KB Output is correct
40 Correct 297 ms 223744 KB Output is correct
41 Correct 83 ms 222648 KB Output is correct
42 Correct 96 ms 222540 KB Output is correct
43 Correct 120 ms 223060 KB Output is correct
44 Correct 125 ms 224500 KB Output is correct
45 Correct 71 ms 120636 KB Output is correct
46 Correct 72 ms 221316 KB Output is correct
47 Correct 118 ms 223828 KB Output is correct
48 Correct 123 ms 224432 KB Output is correct
49 Correct 69 ms 668916 KB Output is correct
50 Correct 63 ms 618296 KB Output is correct
51 Correct 64 ms 669012 KB Output is correct
52 Correct 2 ms 16732 KB Output is correct
53 Correct 67 ms 669012 KB Output is correct
54 Correct 66 ms 668964 KB Output is correct
55 Correct 66 ms 670932 KB Output is correct
56 Correct 65 ms 668852 KB Output is correct
57 Correct 67 ms 670808 KB Output is correct
58 Correct 64 ms 668752 KB Output is correct
59 Correct 66 ms 668896 KB Output is correct
60 Correct 2 ms 18936 KB Output is correct
61 Correct 465 ms 696660 KB Output is correct
62 Correct 956 ms 762052 KB Output is correct
63 Correct 949 ms 759120 KB Output is correct
64 Correct 962 ms 758960 KB Output is correct
65 Correct 373 ms 713232 KB Output is correct
66 Correct 675 ms 724700 KB Output is correct
67 Correct 738 ms 759120 KB Output is correct
68 Correct 2 ms 16732 KB Output is correct
69 Correct 2 ms 16880 KB Output is correct
70 Correct 4 ms 26972 KB Output is correct
71 Correct 3 ms 20828 KB Output is correct
72 Correct 2 ms 16860 KB Output is correct
73 Correct 962 ms 759124 KB Output is correct
74 Correct 902 ms 759120 KB Output is correct
75 Correct 918 ms 758988 KB Output is correct
76 Correct 934 ms 758940 KB Output is correct
77 Execution timed out 5055 ms 758932 KB Time limit exceeded
78 Halted 0 ms 0 KB -