oj.uz

Submission #867710

# Submission time Handle Problem Language Result Execution time Memory
867710 2023-10-29T09:48:48 Z JakobZorz Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 783716 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)||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);
    
    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 16984 KB Output is correct
2 Correct 4 ms 26968 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 3 ms 27076 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 4 ms 27164 KB Output is correct
7 Correct 3 ms 20996 KB Output is correct
8 Correct 3 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 4 ms 26972 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 18780 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16728 KB Output is correct
18 Correct 2 ms 16732 KB Output is correct
19 Correct 3 ms 26972 KB Output is correct
20 Correct 2 ms 20828 KB Output is correct
21 Correct 2 ms 16832 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Correct 4 ms 26968 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 3 ms 27076 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 4 ms 27164 KB Output is correct
7 Correct 3 ms 20996 KB Output is correct
8 Correct 3 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 4 ms 26972 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 18780 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 2 ms 16728 KB Output is correct
18 Correct 2 ms 16732 KB Output is correct
19 Correct 3 ms 26972 KB Output is correct
20 Correct 2 ms 20828 KB Output is correct
21 Correct 2 ms 16832 KB Output is correct
22 Correct 7 ms 41564 KB Output is correct
23 Correct 6 ms 41564 KB Output is correct
24 Correct 6 ms 41464 KB Output is correct
25 Correct 5 ms 41564 KB Output is correct
26 Correct 6 ms 41564 KB Output is correct
27 Correct 6 ms 41468 KB Output is correct
28 Correct 5 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 16984 KB Output is correct
2 Correct 4 ms 26968 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 3 ms 27076 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 4 ms 27164 KB Output is correct
7 Correct 3 ms 20996 KB Output is correct
8 Correct 3 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 4 ms 26972 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 18780 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 7 ms 41564 KB Output is correct
18 Correct 6 ms 41564 KB Output is correct
19 Correct 6 ms 41464 KB Output is correct
20 Correct 5 ms 41564 KB Output is correct
21 Correct 6 ms 41564 KB Output is correct
22 Correct 6 ms 41468 KB Output is correct
23 Correct 5 ms 41564 KB Output is correct
24 Correct 4 ms 29276 KB Output is correct
25 Correct 2 ms 16728 KB Output is correct
26 Correct 2 ms 16732 KB Output is correct
27 Correct 3 ms 26972 KB Output is correct
28 Correct 2 ms 20828 KB Output is correct
29 Correct 2 ms 16832 KB Output is correct
30 Correct 18 ms 72796 KB Output is correct
31 Correct 17 ms 72796 KB Output is correct
32 Correct 17 ms 72792 KB Output is correct
33 Correct 13 ms 72756 KB Output is correct
34 Correct 14 ms 72744 KB Output is correct
35 Correct 15 ms 72792 KB Output is correct
36 Correct 15 ms 72796 KB Output is correct
37 Correct 16 ms 72796 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Correct 4 ms 26968 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 3 ms 27076 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 4 ms 27164 KB Output is correct
7 Correct 3 ms 20996 KB Output is correct
8 Correct 3 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 4 ms 26972 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 18780 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 7 ms 41564 KB Output is correct
18 Correct 6 ms 41564 KB Output is correct
19 Correct 6 ms 41464 KB Output is correct
20 Correct 5 ms 41564 KB Output is correct
21 Correct 6 ms 41564 KB Output is correct
22 Correct 6 ms 41468 KB Output is correct
23 Correct 5 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 17 ms 72796 KB Output is correct
27 Correct 17 ms 72792 KB Output is correct
28 Correct 13 ms 72756 KB Output is correct
29 Correct 14 ms 72744 KB Output is correct
30 Correct 15 ms 72792 KB Output is correct
31 Correct 15 ms 72796 KB Output is correct
32 Correct 16 ms 72796 KB Output is correct
33 Correct 2 ms 16728 KB Output is correct
34 Correct 2 ms 16732 KB Output is correct
35 Correct 3 ms 26972 KB Output is correct
36 Correct 2 ms 20828 KB Output is correct
37 Correct 2 ms 16832 KB Output is correct
38 Correct 82 ms 224008 KB Output is correct
39 Correct 79 ms 223960 KB Output is correct
40 Correct 84 ms 224004 KB Output is correct
41 Correct 78 ms 223828 KB Output is correct
42 Correct 325 ms 224008 KB Output is correct
43 Correct 357 ms 224004 KB Output is correct
44 Correct 384 ms 224260 KB Output is correct
45 Correct 302 ms 224004 KB Output is correct
46 Correct 102 ms 222572 KB Output is correct
47 Correct 93 ms 222548 KB Output is correct
48 Correct 120 ms 223128 KB Output is correct
49 Correct 129 ms 224116 KB Output is correct
50 Correct 62 ms 120728 KB Output is correct
51 Correct 72 ms 221192 KB Output is correct
52 Correct 117 ms 223624 KB Output is correct
53 Correct 124 ms 224420 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 621392 KB Output is correct
2 Correct 66 ms 612576 KB Output is correct
3 Correct 61 ms 619344 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 70 ms 621296 KB Output is correct
6 Correct 65 ms 621504 KB Output is correct
7 Correct 69 ms 621140 KB Output is correct
8 Correct 63 ms 619220 KB Output is correct
9 Correct 63 ms 619200 KB Output is correct
10 Correct 61 ms 620988 KB Output is correct
11 Correct 61 ms 619544 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 2 ms 20828 KB Output is correct
5 Correct 2 ms 16832 KB Output is correct
6 Correct 2 ms 18776 KB Output is correct
7 Correct 473 ms 673084 KB Output is correct
8 Correct 980 ms 764952 KB Output is correct
9 Correct 1014 ms 766036 KB Output is correct
10 Correct 1010 ms 765780 KB Output is correct
11 Correct 383 ms 717912 KB Output is correct
12 Correct 691 ms 730640 KB Output is correct
13 Correct 771 ms 765700 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Correct 4 ms 26968 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 3 ms 27076 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 4 ms 27164 KB Output is correct
7 Correct 3 ms 20996 KB Output is correct
8 Correct 3 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 4 ms 26972 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 18780 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 7 ms 41564 KB Output is correct
18 Correct 6 ms 41564 KB Output is correct
19 Correct 6 ms 41464 KB Output is correct
20 Correct 5 ms 41564 KB Output is correct
21 Correct 6 ms 41564 KB Output is correct
22 Correct 6 ms 41468 KB Output is correct
23 Correct 5 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 17 ms 72796 KB Output is correct
27 Correct 17 ms 72792 KB Output is correct
28 Correct 13 ms 72756 KB Output is correct
29 Correct 14 ms 72744 KB Output is correct
30 Correct 15 ms 72792 KB Output is correct
31 Correct 15 ms 72796 KB Output is correct
32 Correct 16 ms 72796 KB Output is correct
33 Correct 82 ms 224008 KB Output is correct
34 Correct 79 ms 223960 KB Output is correct
35 Correct 84 ms 224004 KB Output is correct
36 Correct 78 ms 223828 KB Output is correct
37 Correct 325 ms 224008 KB Output is correct
38 Correct 357 ms 224004 KB Output is correct
39 Correct 384 ms 224260 KB Output is correct
40 Correct 302 ms 224004 KB Output is correct
41 Correct 102 ms 222572 KB Output is correct
42 Correct 93 ms 222548 KB Output is correct
43 Correct 120 ms 223128 KB Output is correct
44 Correct 129 ms 224116 KB Output is correct
45 Correct 62 ms 120728 KB Output is correct
46 Correct 72 ms 221192 KB Output is correct
47 Correct 117 ms 223624 KB Output is correct
48 Correct 124 ms 224420 KB Output is correct
49 Correct 75 ms 621392 KB Output is correct
50 Correct 66 ms 612576 KB Output is correct
51 Correct 61 ms 619344 KB Output is correct
52 Correct 2 ms 16732 KB Output is correct
53 Correct 70 ms 621296 KB Output is correct
54 Correct 65 ms 621504 KB Output is correct
55 Correct 69 ms 621140 KB Output is correct
56 Correct 63 ms 619220 KB Output is correct
57 Correct 63 ms 619200 KB Output is correct
58 Correct 61 ms 620988 KB Output is correct
59 Correct 61 ms 619544 KB Output is correct
60 Correct 2 ms 18776 KB Output is correct
61 Correct 473 ms 673084 KB Output is correct
62 Correct 980 ms 764952 KB Output is correct
63 Correct 1014 ms 766036 KB Output is correct
64 Correct 1010 ms 765780 KB Output is correct
65 Correct 383 ms 717912 KB Output is correct
66 Correct 691 ms 730640 KB Output is correct
67 Correct 771 ms 765700 KB Output is correct
68 Correct 2 ms 16728 KB Output is correct
69 Correct 2 ms 16732 KB Output is correct
70 Correct 3 ms 26972 KB Output is correct
71 Correct 2 ms 20828 KB Output is correct
72 Correct 2 ms 16832 KB Output is correct
73 Correct 953 ms 783716 KB Output is correct
74 Correct 1000 ms 783188 KB Output is correct
75 Correct 923 ms 782544 KB Output is correct
76 Correct 932 ms 782892 KB Output is correct
77 Execution timed out 5056 ms 783056 KB Time limit exceeded
78 Halted 0 ms 0 KB -