Submission #1212594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212594		guagua0407	Rectangles (IOI19_rect)	C++20	59 / 100	5097 ms	210308 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 dsux(n*m);
    DSU dsuy(n*m);
    vector<bool> used(n*m);
    vector<vector<pair<int,int>>> opx(n);
    vector<vector<pair<int,int>>> opy(n);
    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;
            dsux.go(x*m+y,x,y);
            dsuy.go(x*m+y,x,y);
            active[x][y]=true;
            for(int k=0;k<2;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;
                dsuy.unite(x*m+y,nx*m+ny);
            }
            for(int k=2;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;
                dsux.unite(x*m+y,nx*m+ny);
            }
            st.push_back(x*m+y);
            pos++;
        }
        {
            vector<int> st2;
            for(auto v:st){
                int i=dsux.find(v);
                if(used[i]) continue;
                used[i]=true;
                st2.push_back(i);
                int x1=dsux.mnx[i]-1;
                int x2=dsux.mxx[i]+1;
                int y=v%m;
                if(x1>=0 and x1<n and x2>=0 and x2<n){
                    //cout<<"x "<<y+1<<' '<<x1+1<<' '<<x2+1<<'\n';
                    opx[x1].push_back({x2,y});
                }
            }
            for(auto v:st2){
                used[v]=false;
            }
        }
        {
            vector<int> st2;
            for(auto v:st){
                int i=dsuy.find(v);
                if(used[i]) continue;
                used[i]=true;
                st2.push_back(i);
                int y1=dsuy.mny[i]-1;
                int y2=dsuy.mxy[i]+1;
                int x=v/m;
                if(y1>=0 and y1<m and y2>=0 and y2<m){
                    //cout<<"y "<<x+1<<' '<<y1+1<<' '<<y2+1<<'\n';
                    opy[x].push_back({y1,y2});
                }
            }
            for(auto v:st2){
                used[v]=false;
            }
        }
    }
    ll ans=0;
    for(int x1=0;x1<n;x1++){
        sort(all(opx[x1]));
        int pos=0;
        vector<vector<int>> cnt(m,vector<int>(m));
        for(int x2=x1+2;x2<n;x2++){
            vector<int> pre(m);
            while(pos<(int)opx[x1].size() and opx[x1][pos].f==x2){
                pre[opx[x1][pos].s]++;
                pos++;
            }
            for(int i=1;i<m;i++){
                pre[i]+=pre[i-1];
            }
            for(auto [y1,y2]:opy[x2-1]){
                cnt[y1][y2]++;
                if(cnt[y1][y2]==(x2-x1-1)){
                    if(pre[y2-1]-pre[y1]==(y2-y1-1)){
                        //cout<<x1+1<<' '<<x2+1<<' '<<y1+1<<' '<<y2+1<<'\n';
                        ans++;
                    }
                }
            }
        }
    }
	return ans;
}

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