oj.uz

Submission #153155

# Submission time Handle Problem Language Result Execution time Memory
153155 2019-09-12T15:38:53 Z errorgorn Rectangles (IOI19_rect) C++14
23 / 100
 1182 ms 276680 KB 
    #include "rect.h"
    #include <cstdio>
    #include <vector>
    #include <cstring>
    #include <algorithm>
    #include <utility>
    using namespace std;
    typedef pair<int,int> ii;
    int n,m;
    vector<vector<int> > grid;
    bool visited[2505][2505];
    ii p[2505][2505];
    int r[2505][2505];
    int s[2505][2505];
    int left [2505][2505];
    int right[2505][2505];
    int top[2505][2505];
    int bottom[2505][2505];
    ii parent(ii i){return (i==p[i.first][i.second])?i:p[i.first][i.second]=parent(p[i.first][i.second]);}
    void unions(ii i, ii j){
        i=parent(i),j=parent(j);
        if (i==j) return;
        if (r[i.first][i.second]<r[j.first][j.second]){
            p[i.first][i.second]=j;
            s[j.first][j.second]+=s[i.first][i.second];
            left[j.first][j.second]=min(left[i.first][i.second],left[j.first][j.second]);
            right[j.first][j.second]=max(right[i.first][i.second],right[j.first][j.second]);
            top[j.first][j.second]=max(top[i.first][i.second],top[j.first][j.second]);
            bottom[j.first][j.second]=min(bottom[i.first][i.second],bottom[j.first][j.second]);
        }
        else{
            p[j.first][j.second]=i;
            s[i.first][i.second]+=s[j.first][j.second];
            left[i.first][i.second]=min(left[i.first][i.second],left[j.first][j.second]);
            right[i.first][i.second]=max(right[i.first][i.second],right[j.first][j.second]);
            top[i.first][i.second]=max(top[i.first][i.second],top[j.first][j.second]);
            bottom[i.first][i.second]=min(bottom[i.first][i.second],bottom[j.first][j.second]);
            if (r[i.first][i.second]==r[j.first][j.second]) r[i.first][i.second]++;
        }
    }
    struct horST{
        int st[2505][12];
        horST(int i){
            memset(st,-1,sizeof(st));
            for (int x=0;x<m;x++){
                st[x][0]=grid[i][x];
            }
            int add=1;
            int row=0;
            while (st[add][row]!=-1){
                for (int x=add;st[x][row]!=-1;x++){
                    st[x-add][row+1]=max(st[x-add][row],st[x][row]);
                }
                row++;
                add<<=1;
            }
        }
        int query(int i,int j){
            j=j-i+1;
            int row=31-__builtin_clz(j);
            j-=1<<row;
            return max(st[i][row],st[i+j][row]);
        }
    };
    struct verST{
        int st[2505][12];
        verST(int i){
            memset(st,-1,sizeof(st));
            for (int x=0;x<m;x++){
                st[x][0]=grid[x][i];
            }
            int add=1;
            int row=0;
            while (st[add][row]!=-1){
                for (int x=add;st[x][row]!=-1;x++){
                    st[x-add][row+1]=max(st[x-add][row],st[x][row]);
                }
                row++;
                add<<=1;
            }
        }
        int query(int i,int j){
            j=j-i+1;
            int row=31-__builtin_clz(j);
            j-=1<<row;
            return max(st[i][row],st[i+j][row]);
        }
    };
    const int dx[]={1,-1,0,0};
    const int dy[]={0,0,1,-1};
    ii temp;
    long long ans=0;
    bool side[2505];
    horST *horr;
    long long count_rectangles(vector<vector<int> > in) {
        grid=in;
        n=grid.size();
        m=grid[0].size();
        for (int x=0;x<n;x++)
            for (int y=0;y<m;y++)
                if (grid[x][y]>1) goto skip1;
        for (int x=0;x<n;x++){
            for (int y=0;y<m;y++){
                p[x][y]=ii(x,y);
                r[x][y]=0;
                s[x][y]=1;
                left[x][y]=x;
                right[x][y]=x;
                top[x][y]=y;
                bottom[x][y]=y;
            }
        }
        int xx,yy;
        for (int x=0;x<n;x++){
            for (int y=0;y<m;y++){
                if (grid[x][y]==1) continue;
                for (int z=0;z<4;z++){
                    xx=x+dx[z];
                    yy=y+dy[z];
                    if (xx<0 || n<=xx || yy<0 || m<=yy) continue;
                    if (grid[xx][yy]==0) unions(ii(x,y),ii(xx,yy));
                }
            }
        }
        for (int x=1;x<n-1;x++){
            for (int y=1;y<m-1;y++){
                if (grid[x][y]==1) continue;
                temp=parent(ii(x,y));
                xx=temp.first;
                yy=temp.second;
                if (visited[xx][yy]) continue;
                visited[xx][yy]=true;
                if (left[xx][yy]==0 || right[xx][yy]==n-1 || bottom[xx][yy]==0 || top[xx][yy]==m-1) continue;
                if ((right[xx][yy]-left[xx][yy]+1)*(top[xx][yy]-bottom[xx][yy]+1)==s[xx][yy]) ans++;
            }
        }
        return ans;
        skip1:
        if (n==1 || n==2) return 0;
        if (n>3) goto skip2;
        for (int x=1;x<m-1;x++){
            side[x]=(min(grid[0][x],grid[2][x])>grid[1][x]);
        }
        horr=new horST(1);
        for (int x=1;x<m-1;x++){
            if (!side[x]) continue;
            for (int y=x;y<m-1;y++){
                if (!side[y]) break;
                if (horr->query(x,y)<min(grid[1][x-1],grid[1][y+1])) ans++;
            }
        }
        return ans;
        skip2:
        horST *hors[205];
        verST *vers[205];
        for (int x=0;x<m;x++){
            hors[x]=new horST(x);
        }
        for (int x=0;x<n;x++){
            vers[x]=new verST(x);
        }
        for (int x1=1;x1<m-1;x1++){
            for (int x2=x1;x2<m-1;x2++){
                for (int y1=1;y1<n-1;y1++){
                    for (int y2=y1;y2<n-1;y2++){
                        if (hors[y2]->query(x1,x2)>=min(grid[y2][x1-1],grid[y2][x2+1])) break;
                        for (int z=x1;z<=x2;z++){
                            if (vers[z]->query(y1,y2)>=min(grid[y1-1][z],grid[y2+1][z])) goto _end;
                        }
                        ans++;
                        _end:;
                    }
                }
            }
        }
        return ans;
    }

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Runtime error 24 ms 10616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Runtime error 24 ms 10616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Runtime error 24 ms 10616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Runtime error 24 ms 10616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 524 KB Output is correct
2 Correct 11 ms 504 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 441 ms 134552 KB Output is correct
3 Correct 871 ms 275716 KB Output is correct
4 Correct 871 ms 276532 KB Output is correct
5 Correct 870 ms 276680 KB Output is correct
6 Correct 585 ms 133820 KB Output is correct
7 Correct 1119 ms 265788 KB Output is correct
8 Correct 1182 ms 270400 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 1272 KB Output is correct
12 Correct 3 ms 1272 KB Output is correct
13 Correct 2 ms 632 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Runtime error 24 ms 10616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -