Submission #1144165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144165		AdamGS	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	2927 ms	67912 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
vector<vector<int>> a;
vector<vector<int>> sum[82];
int n,m;
// mask = D*21 + L*9 + G*3 + P

bool check(int mask, int x, int y){
    pair<int,int> rx; pair<int,int> ry;
    ry.second = min(m,y+mask%3); mask/=3;
    rx.first = max(1,x-mask%3); mask/=3;
    ry.first = max(1,y-mask%3); mask/=3;
    rx.second = min(n,x+mask%3); mask/=3;
    int cnt=0;
    for (int z=0;z<4;z++){
        if (!(rx.first<=x+d[z][0] && x+d[z][0]<=rx.second && ry.first<=y+d[z][1] && y+d[z][1]<=ry.second))continue;
        int maks=0;
        for (int w=0;w<4;w++){
            int nx=x+d[z][0]+d[w][0]; int ny=y+d[z][1]+d[w][1];
            if (rx.first<=nx && nx<=rx.second && ry.first<=ny && ny<=ry.second){
                if (a[nx][ny] < a[x+d[z][0]][y+d[z][1]])maks=max(maks,a[nx][ny]);
            }
        }
        if (maks==a[x][y])cnt++;
    }
    return cnt!=1;
}

int code(int d, int l, int g, int p){
    int odp=min(2,p);
    odp+=min(2,g)*3;
    odp+=min(2,l)*9;
    odp+=min(2,d)*27;
    return odp;
}

int suma(int x1, int y1, int x2, int y2, int mask){
    return sum[mask][x2][y2]-sum[mask][x1-1][y2]-sum[mask][x2][y1-1]+sum[mask][x1-1][y1-1];
}

// all
int calc3(int x1, int y1, int x2, int y2){
    int odp=0;
    for (int x=0;x<min(5,x2-x1+1);x++){
        for (int y=0;y<min(5,y2-y1+1);y++){
            pair<int,int> rx,ry;

            if (x==0)rx={x1,x1};
            else if (x==1) rx={x1+1,x1+1};
            else if (x==4) rx={x1+2,x2-2};
            else if (x==3) rx={x2-1,x2-1};
            else if (x==2) rx={x2,x2};

            if (y==0)ry={y1,y1};
            else if (y==1) ry={y1+1,y1+1};
            else if (y==4) ry={y1+2,y2-2};
            else if (y==3) ry={y2-1,y2-1};
            else if (y==2) ry={y2,y2};
            odp += suma(rx.first,ry.first,rx.second,ry.second,code(x2-rx.first,ry.first-y1,rx.first-x1,y2-ry.first));
        }
    }
    return odp;
}

// y2
int calc2(int x1, int x2, int y2){
    int odp=0;
    for (int x=0;x<min(5,x2-x1+1);x++){
        pair<int,int> rx;
        if (x==0)rx={x1,x1};
        else if (x==1) rx={x1+1,x1+1};
        else if (x==4) rx={x1+2,x2-2};
        else if (x==3) rx={x2-1,x2-1};
        else if (x==2) rx={x2,x2};

        for (int y=1;y<3;y++){
            pair<int,int> ry;
            if (y==1) ry={y2-1,y2-1};
            else if (y==2) ry={y2,y2};
            odp += suma(rx.first,ry.first,rx.second,ry.second,code(x2-rx.first,100,rx.first-x1,y2-ry.first));
        }
        int mask=code(x2-rx.first,100,rx.first-x1,100);
        odp += sum[mask][rx.second][y2-2]-sum[mask][rx.first-1][y2-2];
    }
    return odp;
}

// y1
int calc1(int x1, int y1, int x2){
    int odp=0;
    for (int x=0;x<min(5,x2-x1+1);x++){
        pair<int,int> rx;
        if (x==0)rx={x1,x1};
        else if (x==1) rx={x1+1,x1+1};
        else if (x==4) rx={x1+2,x2-2};
        else if (x==3) rx={x2-1,x2-1};
        else if (x==2) rx={x2,x2};

        for (int y=0;y<2;y++){
            pair<int,int> ry;

            if (y==0)ry={y1,y1};
            else if (y==1) ry={y1+1,y1+1};
            odp += suma(rx.first,ry.first,rx.second,ry.second,code(x2-rx.first,ry.first-y1,rx.first-x1,100));
        }
        
        int mask = code(x2-rx.first,100,rx.first-x1,100);
        odp += -sum[mask][rx.second][y1+1]+sum[mask][rx.first-1][y1+1];
    }
    return odp;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    // n mniejsze
    vector<int> empt2(max(m,n)+3,0);
    vector<vector<int>> empt(min(n,m)+3,empt2);
    a=empt;
    for (int x=0;x<82;x++)sum[x]=empt;
    for (int x=1;x<=n;x++){
        for (int y=1;y<=m;y++){
            if (n<=m)cin>>a[x][y];
            else cin >> a[y][x];
        }
    }
    if (n>m)swap(n,m);
    for (int mask=0;mask<81;mask++){
        for (int x=1;x<=n;x++){
            for (int y=1;y<=m;y++){
                sum[mask][x][y]=sum[mask][x-1][y]+sum[mask][x][y-1]-sum[mask][x-1][y-1];
                sum[mask][x][y]+=check(mask,x,y);
            }
        }
    }
    ll odp=0;
    map<int,int> cnt;
    for (int x1=1;x1<=n;x1++){
        for (int x2=x1;x2<=n;x2++){
            cnt.clear();
            for (int y2=1;y2<=m;y2++){
                odp += cnt[calc2(x1,x2,y2)];

                if (y2>3)cnt[1-calc1(x1,y2-3,x2)]++;

                for (int y1=max(1,y2-3);y1<=y2;y1++){
                    if (calc3(x1,y1,x2,y2)==1){
                        odp++;
                    }
                }
            }
        }
    }
    /*for (int x=1;x<=3;x++){
        cout << check(code(0,x-1,0,3-x),1,x) << ' ';
    }
    cout << '\n';
    cout << calc(1,1,1,3) << '\n';*/
    cout << odp << '\n';
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 56 / 56
• Subtask 5: 20 / 20