Submission #1212461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212461		guagua0407	Rectangles (IOI19_rect)	C++20	13 / 100	1338 ms	303988 KiB

rect

#include "rect.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

namespace{
    struct DSU{
        vector<int> e;
        vector<int> mnx,mny,mxx,mxy;
        DSU(int n){
            e=vector<int>(n,-1);
            mnx=mny=mxx=mxy=vector<int>(n);
        }
        void go(int i,int x,int y){
            mnx[i]=mxx[i]=x;
            mny[i]=mxy[i]=y;
        }
        int find(int x){
            return (e[x]<0?x:e[x]=find(e[x]));
        }
        bool unite(int a,int b){
            a=find(a);
            b=find(b);
            if(a==b) return false;
            if(e[a]>e[b]) swap(a,b);
            e[a]+=e[b];
            e[b]=a;
            mnx[a]=min(mnx[a],mnx[b]);
            mny[a]=min(mny[a],mny[b]);
            mxx[a]=max(mxx[a],mxx[b]);
            mxy[a]=max(mxy[a],mxy[b]);
            return true;
        }
    };
}

long long count_rectangles(std::vector<std::vector<int> > a) {
    int n=(int)a.size();
    int m=(int)a[0].size();
    vector<pair<int,pair<int,int>>> vec;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            vec.push_back({a[i][j],{i,j}});
        }
    }
    sort(all(vec));
    vector<vector<bool>> active(n,vector<bool>(m));
    DSU dsu(n*m);
    vector<bool> used(n*m);
    ll ans=0;
    auto ok=[&](int i){
        ll sz=-dsu.e[i];
        ll sz2=1ll*(dsu.mxx[i]-dsu.mnx[i]+1)*(dsu.mxy[i]-dsu.mny[i]+1);
        return (sz==sz2 and dsu.mnx[i]!=0 and dsu.mxx[i]!=n-1 and dsu.mny[i]!=0 and dsu.mxy[i]!=m-1);
    };
    for(int pos=0;pos<n*m;){
        int cur=vec[pos].f;
        vector<int> st;
        while(pos<n*m and vec[pos].f==cur){
            auto [x,y]=vec[pos].s;
            dsu.go(x*m+y,x,y);
            active[x][y]=true;
            for(int k=0;k<4;k++){
                int nx=x+dx[k];
                int ny=y+dy[k];
                if(nx<0 or nx>=n or ny<0 or ny>=m or !active[nx][ny]) continue;
                dsu.unite(x*m+y,nx*m+ny);
            }
            st.push_back(x*m+y);
            pos++;
        }
        vector<int> st2;
        for(auto v:st){
            int i=dsu.find(v);
            if(used[i]) continue;
            used[i]=true;
            st2.push_back(i);
            if(ok(i)){
                //cout<<cur<<' '<<i/m+1<<' '<<i%m+1<<'\n';
                ans++;
            }
        }
        for(auto v:st2){
            used[v]=false;
        }
    }
	return ans;
}

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