Submission #771378

#	Time	Username	Problem	Language	Result	Execution time	Memory
771378		TimDee	Rectangles (IOI19_rect)	C++17	72 / 100	3280 ms	1048576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int _n, _m;

struct DSU {
 
    vector<int> p;
    vector<int> r;
    vector<int> sz, minr, maxr, minc, maxc, vis;
    
    DSU(int N, int M) {
        int n=N*M;
        p.assign(n,0);
        r.assign(n,0);
        for (int i=0; i<n; ++i) p[i]=i;
        sz.assign(n,1);
        minr.assign(n,1);
        minc.assign(n,1);
        maxr.assign(n,1);
        maxc.assign(n,1);
        vis.assign(n,0);
        for (int i=0; i<n; ++i) {
            minr[i]=maxr[i]=i/N;
            minc[i]=maxc[i]=i%M;
        }
    }

    int get(int i) {
        return p[i]==i ? i : get(p[i]);    
    }

    int calc(int i, int j) {
        int a=i*2500+j;
        a=get(a);
        if (vis[a]) return 0;
        vis[a]=1;
        if (minr[a]==0 || minc[a]==0 || maxc[a]==_m-1 || maxr[a]==_n-1) return 0;
        return sz[a]==(maxr[a]-minr[a]+1)*(maxc[a]-minc[a]+1);
    }
    
    void uni(int i, int j, int x, int y) {
            
        int a=i*2500+j, b=x*2500+y;

        a=get(a);
        b=get(b);
        if (a==b) return;
        
        if (r[a]==r[b]) r[a]++;
        
        if (r[a]<r[b]) {
            swap(a,b);
        }
        p[b]=a;
        sz[a]+=sz[b];
        minr[a]=min(minr[a],minr[b]);
        maxr[a]=max(maxr[a],maxr[b]);
        minc[a]=min(minc[a],minc[b]);
        maxc[a]=max(maxc[a],maxc[b]);
        
    }
    
};

ll count_rectangles(vector<vector<int>>a) {
    int n=a.size(), m=a[0].size(); 
    _n=n, _m=m;
    int mx=0;
    if (n<=2 || m<=2) return 0;
    if (n==3) {
        ll ans=0;
        int left=0;
        for (int i=1; i<m-1; ++i) {
            mx=0;
            for (int j=i; j<m-1; ++j) {
                mx=max(mx,a[1][j]);
                if (a[1][j]>=min(a[0][j],a[2][j])) break;
                if (mx<min(a[1][i-1],a[1][j+1])) ++ans;
            }
        }
        return ans;
    }
    for (int i=0; i<n; ++i) {
        for (int j=0; j<m; ++j) mx=max(mx,a[i][j]);
    }
    if (mx==0) return 0;
    if (mx==1) {
        DSU dsu(2500,2500);
        vector<vector<int>> vis(n,vector<int>(m,0));
        queue<pair<int,int>> q;
        for (int i=0; i<n; ++i) {
            for (int j=0; j<m; ++j) {
                if (a[i][j]==0) q.push({i,j});
            }
        }
        while (!q.empty()) {
            auto u=q.front(); q.pop();
            int i=u.first, j=u.second;
            vis[i][j]=1;
            if (i && a[i-1][j]==0) {
                dsu.uni(i,j,i-1,j);
                vis[i-1][j]=1;
            }
            if (i<n-1 && a[i+1][j]==0) {
                dsu.uni(i,j,i+1,j);
                vis[i+1][j]=1;
            }
            if (j && a[i][j-1]==0) {
                dsu.uni(i,j,i,j-1);
                vis[i][j-1]=1;
            }
            if (j<m-1 && a[i][j+1]==0) {
                dsu.uni(i,j,i,j+1);
                vis[i][j+1]=1;
            }
        }
        ll ans=0;
        for (int i=1; i<n-1; ++i) {
            for (int j=1; j<m-1; ++j) {
                if (a[i][j]==0) ans+=dsu.calc(i,j);
            }
        }
        return ans;
    }

    ll ans=0;

    vector<vector<bitset<700>>> row(n,vector<bitset<700>>(m));
    vector<vector<bitset<700>>> col(m,vector<bitset<700>>(n));
    vector<int> dp(n,0);
    for (int i=1; i<n-1; ++i) {
        for (int l=1; l<m-1; ++l) {
            mx=0;
            for (int r=l; r<m-1; ++r) {mx=max(mx,a[i][r]); row[i][l][r]=mx<min(a[i][l-1],a[i][r+1]); }
        }
    }
    for (int i=1; i<m-1; ++i) {
        for (int l=1; l<n-1; ++l) {
            mx=0;
            for (int r=l; r<n-1; ++r) {mx=max(mx,a[r][i]); col[i][l][r]=mx<min(a[l-1][i],a[r+1][i]); }
        }
    }

    for (int x=1; x<n-1; ++x) {
        for (int y=1; y<m-1; ++y) {
            dp.assign(n,0);
            for (int len=1; x+len<n; ++len) {
                for (int j=y; j<m-1; ++j) {
                    if (col[j][x][x+len-1]) dp[len]++;
                    else break;
                }
            }
            for (int len=1; y+len<m; ++len) {
                for (int i=x; i<n-1; ++i) {
                    if (row[i][y][y+len-1]) { if (dp[i-x+1]>=len) ++ans; }
                    else break;
                }
            }
        }
    }

    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:74:13: warning: unused variable 'left' [-Wunused-variable]
   74 |         int left=0;
      |             ^~~~

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