oj.uz

Submission #867705

# Submission time Handle Problem Language Result Execution time Memory
867705 2023-10-29T09:34:31 Z JakobZorz Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 472040 KB 
#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];
short gap_down_min[2500][2500][12];
int gap_left[2500][2500];
int gap_up[2500][2500];
short gap_up_max[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];
                }
            }
        }
    }
}

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){
    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);
    
    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 12636 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18776 KB Output is correct
6 Correct 3 ms 18980 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 18876 KB Output is correct
9 Correct 2 ms 18776 KB Output is correct
10 Correct 2 ms 18776 KB Output is correct
11 Correct 3 ms 18776 KB Output is correct
12 Correct 3 ms 18776 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 1 ms 12728 KB Output is correct
18 Correct 2 ms 12636 KB Output is correct
19 Correct 2 ms 18780 KB Output is correct
20 Correct 2 ms 14684 KB Output is correct
21 Correct 1 ms 12632 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18776 KB Output is correct
6 Correct 3 ms 18980 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 18876 KB Output is correct
9 Correct 2 ms 18776 KB Output is correct
10 Correct 2 ms 18776 KB Output is correct
11 Correct 3 ms 18776 KB Output is correct
12 Correct 3 ms 18776 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 1 ms 12728 KB Output is correct
18 Correct 2 ms 12636 KB Output is correct
19 Correct 2 ms 18780 KB Output is correct
20 Correct 2 ms 14684 KB Output is correct
21 Correct 1 ms 12632 KB Output is correct
22 Correct 4 ms 29276 KB Output is correct
23 Correct 5 ms 29276 KB Output is correct
24 Correct 4 ms 29120 KB Output is correct
25 Correct 4 ms 29276 KB Output is correct
26 Correct 4 ms 29276 KB Output is correct
27 Correct 5 ms 29276 KB Output is correct
28 Correct 4 ms 29272 KB Output is correct
29 Correct 3 ms 19032 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18776 KB Output is correct
6 Correct 3 ms 18980 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 18876 KB Output is correct
9 Correct 2 ms 18776 KB Output is correct
10 Correct 2 ms 18776 KB Output is correct
11 Correct 3 ms 18776 KB Output is correct
12 Correct 3 ms 18776 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 4 ms 29276 KB Output is correct
18 Correct 5 ms 29276 KB Output is correct
19 Correct 4 ms 29120 KB Output is correct
20 Correct 4 ms 29276 KB Output is correct
21 Correct 4 ms 29276 KB Output is correct
22 Correct 5 ms 29276 KB Output is correct
23 Correct 4 ms 29272 KB Output is correct
24 Correct 3 ms 19032 KB Output is correct
25 Correct 1 ms 12728 KB Output is correct
26 Correct 2 ms 12636 KB Output is correct
27 Correct 2 ms 18780 KB Output is correct
28 Correct 2 ms 14684 KB Output is correct
29 Correct 1 ms 12632 KB Output is correct
30 Correct 20 ms 46172 KB Output is correct
31 Correct 21 ms 46220 KB Output is correct
32 Correct 21 ms 46168 KB Output is correct
33 Correct 9 ms 45916 KB Output is correct
34 Correct 11 ms 46120 KB Output is correct
35 Correct 11 ms 46172 KB Output is correct
36 Correct 11 ms 46172 KB Output is correct
37 Correct 11 ms 46168 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18776 KB Output is correct
6 Correct 3 ms 18980 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 18876 KB Output is correct
9 Correct 2 ms 18776 KB Output is correct
10 Correct 2 ms 18776 KB Output is correct
11 Correct 3 ms 18776 KB Output is correct
12 Correct 3 ms 18776 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 4 ms 29276 KB Output is correct
18 Correct 5 ms 29276 KB Output is correct
19 Correct 4 ms 29120 KB Output is correct
20 Correct 4 ms 29276 KB Output is correct
21 Correct 4 ms 29276 KB Output is correct
22 Correct 5 ms 29276 KB Output is correct
23 Correct 4 ms 29272 KB Output is correct
24 Correct 3 ms 19032 KB Output is correct
25 Correct 20 ms 46172 KB Output is correct
26 Correct 21 ms 46220 KB Output is correct
27 Correct 21 ms 46168 KB Output is correct
28 Correct 9 ms 45916 KB Output is correct
29 Correct 11 ms 46120 KB Output is correct
30 Correct 11 ms 46172 KB Output is correct
31 Correct 11 ms 46172 KB Output is correct
32 Correct 11 ms 46168 KB Output is correct
33 Correct 1 ms 12728 KB Output is correct
34 Correct 2 ms 12636 KB Output is correct
35 Correct 2 ms 18780 KB Output is correct
36 Correct 2 ms 14684 KB Output is correct
37 Correct 1 ms 12632 KB Output is correct
38 Correct 60 ms 135272 KB Output is correct
39 Correct 60 ms 135760 KB Output is correct
40 Correct 64 ms 135336 KB Output is correct
41 Correct 58 ms 135428 KB Output is correct
42 Correct 658 ms 135592 KB Output is correct
43 Correct 611 ms 135508 KB Output is correct
44 Correct 610 ms 135764 KB Output is correct
45 Correct 574 ms 135500 KB Output is correct
46 Correct 67 ms 134476 KB Output is correct
47 Correct 70 ms 134228 KB Output is correct
48 Correct 95 ms 134516 KB Output is correct
49 Correct 99 ms 135756 KB Output is correct
50 Correct 48 ms 75600 KB Output is correct
51 Correct 57 ms 133012 KB Output is correct
52 Correct 96 ms 135120 KB Output is correct
53 Correct 104 ms 135764 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 289628 KB Output is correct
2 Correct 33 ms 287568 KB Output is correct
3 Correct 32 ms 293456 KB Output is correct
4 Correct 2 ms 12792 KB Output is correct
5 Correct 35 ms 293460 KB Output is correct
6 Correct 32 ms 299088 KB Output is correct
7 Correct 32 ms 297308 KB Output is correct
8 Correct 33 ms 297248 KB Output is correct
9 Correct 33 ms 297300 KB Output is correct
10 Correct 33 ms 297008 KB Output is correct
11 Correct 33 ms 299088 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12728 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 1 ms 12632 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 390 ms 378216 KB Output is correct
8 Correct 849 ms 471528 KB Output is correct
9 Correct 880 ms 471756 KB Output is correct
10 Correct 854 ms 472040 KB Output is correct
11 Correct 374 ms 389968 KB Output is correct
12 Correct 579 ms 452848 KB Output is correct
13 Correct 675 ms 471900 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18776 KB Output is correct
6 Correct 3 ms 18980 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 18876 KB Output is correct
9 Correct 2 ms 18776 KB Output is correct
10 Correct 2 ms 18776 KB Output is correct
11 Correct 3 ms 18776 KB Output is correct
12 Correct 3 ms 18776 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 4 ms 29276 KB Output is correct
18 Correct 5 ms 29276 KB Output is correct
19 Correct 4 ms 29120 KB Output is correct
20 Correct 4 ms 29276 KB Output is correct
21 Correct 4 ms 29276 KB Output is correct
22 Correct 5 ms 29276 KB Output is correct
23 Correct 4 ms 29272 KB Output is correct
24 Correct 3 ms 19032 KB Output is correct
25 Correct 20 ms 46172 KB Output is correct
26 Correct 21 ms 46220 KB Output is correct
27 Correct 21 ms 46168 KB Output is correct
28 Correct 9 ms 45916 KB Output is correct
29 Correct 11 ms 46120 KB Output is correct
30 Correct 11 ms 46172 KB Output is correct
31 Correct 11 ms 46172 KB Output is correct
32 Correct 11 ms 46168 KB Output is correct
33 Correct 60 ms 135272 KB Output is correct
34 Correct 60 ms 135760 KB Output is correct
35 Correct 64 ms 135336 KB Output is correct
36 Correct 58 ms 135428 KB Output is correct
37 Correct 658 ms 135592 KB Output is correct
38 Correct 611 ms 135508 KB Output is correct
39 Correct 610 ms 135764 KB Output is correct
40 Correct 574 ms 135500 KB Output is correct
41 Correct 67 ms 134476 KB Output is correct
42 Correct 70 ms 134228 KB Output is correct
43 Correct 95 ms 134516 KB Output is correct
44 Correct 99 ms 135756 KB Output is correct
45 Correct 48 ms 75600 KB Output is correct
46 Correct 57 ms 133012 KB Output is correct
47 Correct 96 ms 135120 KB Output is correct
48 Correct 104 ms 135764 KB Output is correct
49 Correct 37 ms 289628 KB Output is correct
50 Correct 33 ms 287568 KB Output is correct
51 Correct 32 ms 293456 KB Output is correct
52 Correct 2 ms 12792 KB Output is correct
53 Correct 35 ms 293460 KB Output is correct
54 Correct 32 ms 299088 KB Output is correct
55 Correct 32 ms 297308 KB Output is correct
56 Correct 33 ms 297248 KB Output is correct
57 Correct 33 ms 297300 KB Output is correct
58 Correct 33 ms 297008 KB Output is correct
59 Correct 33 ms 299088 KB Output is correct
60 Correct 2 ms 14684 KB Output is correct
61 Correct 390 ms 378216 KB Output is correct
62 Correct 849 ms 471528 KB Output is correct
63 Correct 880 ms 471756 KB Output is correct
64 Correct 854 ms 472040 KB Output is correct
65 Correct 374 ms 389968 KB Output is correct
66 Correct 579 ms 452848 KB Output is correct
67 Correct 675 ms 471900 KB Output is correct
68 Correct 1 ms 12728 KB Output is correct
69 Correct 2 ms 12636 KB Output is correct
70 Correct 2 ms 18780 KB Output is correct
71 Correct 2 ms 14684 KB Output is correct
72 Correct 1 ms 12632 KB Output is correct
73 Correct 882 ms 468648 KB Output is correct
74 Correct 818 ms 465216 KB Output is correct
75 Correct 843 ms 465428 KB Output is correct
76 Correct 826 ms 465300 KB Output is correct
77 Execution timed out 5043 ms 465320 KB Time limit exceeded
78 Halted 0 ms 0 KB -