Submission #153162

#	Time	Username	Problem	Language	Result	Execution time	Memory
153162		errorgorn	Rectangles (IOI19_rect)	C++14	0 / 100	501 ms	363392 KiB

rect

#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();
    horST *hors[205];
    verST *vers[205];
    for (int x=0;x<n;x++){
        hors[x]=new horST(x);
    }
    for (int x=0;x<m;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++){
                    //printf("%d %d %d %d %d %d\n",y2,x1,x2,hors[y2]->query(x1,x2),grid[y2][x1-1],grid[y2][x2+1]);
                    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;
                    }
                    //printf("final: %d %d %d %d\n",x1,x2,y1,y2);
                    ans++;
                    _end:;
                }
            }
        }
    }
    return ans;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28