Submission #1134929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134929		Unforgettablepl	Sandcastle 2 (JOI22_ho_t5)	C++20	9 / 100	22 ms	20160 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef long double ld;

const int INF = 1e10;


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int h,w;
    cin >> h >> w;
    vector arr(min(h,w)+1,vector<int>(max(h,w)+1));
    if(h>w) {
        for(int i=1;i<=h;i++) {
            for(int j=1;j<=w;j++) {
                cin>>arr[j][i];
            }
        }
        swap(h,w);
    } else {
        for(int i=1;i<=h;i++) {
            for(int j=1;j<=w;j++) {
                cin>>arr[i][j];
            }
        }
    }
    vector DP(h+1,vector(h+1,vector(w+1,vector(2,0ll))));
    int ans = h*w;
    for(int k=1;k<=w;k++) {
        for(int i=1;i<=h;i++) {
            // Upwards
            int tolerance = 0;
            for(int j=i-1;j;j--) {
                if(arr[j][k]>arr[j+1][k]) {
                    if(tolerance)break;
                    tolerance=1;
                    ans+=i-j-1;
                }
                DP[i][j][k][tolerance]=1;
            }
            if(tolerance==0)ans+=i-1;
            // Downwards
            tolerance = 0;
            for(int j=i+1;j<=h;j++) {
                if(arr[j][k]>arr[j-1][k]) {
                    if(tolerance)break;
                    tolerance=1;
                    ans+=j-i-1;
                }
                DP[i][j][k][tolerance]=1;
            }
            if(tolerance==0)ans+=h-i;
        }
    }
    for(int i=1;i<=h;i++) {
        for(int j=1;j<=h;j++) {
            for(int k=1;k<=w;k++) {
                for(int tolerance=0;tolerance<=1;tolerance++) {
                    DP[i][j][k][tolerance]+=DP[i][j][k-1][tolerance];
                }
            }
        }
    }
    vector forwards(h+1,vector(w+1,0));
    vector backwards(h+1,vector(w+1,0));
    for(int i=1;i<=h;i++) {
        for(int j=2;j<=w;j++) {
            if(arr[i][j]>arr[i][j-1])backwards[i][j]=1;
            else forwards[i][j]=1;
            forwards[i][j]+=forwards[i][j-1];
            backwards[i][j]+=backwards[i][j-1];
        }
    }
    for(int i=1;i<=h;i++) {
        for(int j=1;j<=h;j++) {
            for(int k=1;k<=w;k++) {
                auto getTolerant = [&](const int x) {
                    return (backwards[i][x]-backwards[i][k]-x+k) + (forwards[j][x]-forwards[j][k]-x+k);
                };
                // 0 Tolerance
                if(DP[i][j][k][0]-DP[i][j][k-1][0]) {
                    int r = k;
                    for(int jump=(1ll<<15);jump;jump/=2) {
                        if(r+jump<=w and getTolerant(r+jump)==0)r+=jump;
                    }
                    int rr = r;
                    for(int jump=(1ll<<15);jump;jump/=2) {
                        if(rr+jump<=w and getTolerant(rr+jump)<=1)rr+=jump;
                    }
                    ans+=DP[j][i][r][1]-DP[j][i][k][1] + DP[j][i][rr][0] - DP[j][i][k][0];
                }
                // 1 Tolerance
                else if(DP[i][j][k][1]-DP[i][j][k-1][1]) {
                    int r = k;
                    for(int jump=(1ll<<15);jump;jump/=2) {
                        if(r+jump<=w and getTolerant(r+jump)==0)r+=jump;
                    }
                    ans+=DP[j][i][r][0]-DP[j][i][k][0];
                }
            }
        }
    }
    for(int i=1;i<=h;i++) {
        for(int j=1;j<=w;j++) {
            int r = j;
            for(int jump=(1ll<<15);jump;jump/=2) {
                if(r+jump<=w and forwards[i][r+jump]-forwards[i][j]==r+jump-j)r+=jump;
            }
            ans+=r-j;
            r = j;
            for(int jump=(1ll<<15);jump;jump/=2) {
                if(r+jump<=w and backwards[i][r+jump]-backwards[i][j]==r+jump-j)r+=jump;
            }
            ans+=r-j;
        }
    }
    cout << ans << '\n';
}

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