Submission #1179629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179629		patgra	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	463 ms	64524 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr int maxn = 5e4 + 7;
int h, w;
int arr[maxn];
int addHere[maxn][3][3][3][3]; // l t r b
int prefSum[maxn][3][3][3][3], prefSumCol[maxn][3][3][3][3], prefSumRow[maxn][3][3][3][3]; // count wch == 1
int cntMap[maxn * 2];

void transpose() {
    vector<int> og(maxn);
    rep(i, 0, maxn) og[i] = arr[i];
    rep(i, 0, h) rep(j, 0, w) arr[j * h + i] = og[i * w + j];
    swap(h, w);
}

int rectSum(int l, int t, int r, int b, int ml, int tt, int rr, int bb) {
    int ans = prefSum[b * w + r][ml][tt][rr][bb];
    if(l) ans -= prefSum[b * w + l - 1][ml][tt][rr][bb];
    if(t) ans -= prefSum[t * w + r - w][ml][tt][rr][bb];
    if(l && t) ans += prefSum[t * w + l - 1 - w][ml][tt][rr][bb];
    return ans;
}
int rowSum(int l, int tb, int r, int ml, int tt, int rr, int bb) {
    int ans = prefSumRow[tb * w + r][ml][tt][rr][bb];
    if(l) ans -= prefSumRow[tb * w + l - 1][ml][tt][rr][bb];
    return ans;
}
int colSum(int lr, int t, int b, int ml, int tt, int rr, int bb) {
    int ans = prefSumCol[b * w + lr][ml][tt][rr][bb];
    if(t) ans -= prefSumCol[t * w + lr - w][ml][tt][rr][bb];
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> h >> w;
    rep(i, 0, h) rep(j, 0, w) cin >> (arr[i * w + j]);
    if(h > w) transpose();

    rep(i, 0, h) rep(j, 0, w) rep(l, 0, 3) rep(t, 0, 3) rep(r, 0, 3) rep(b, 0, 3) {
        int myVal = arr[i * w + j];
        int wch = 0;
        if(j && l && myVal < arr[i * w + j - 1]) {
            int vall = arr[i * w + j - 1];
            int maxl = myVal;
            if(l > 1 && j > 1 && arr[i * w + j - 2] < vall) maxl =  ((maxl > arr[i * w + j - 2]) ? (maxl) : (arr[i * w + j - 2]));
            if(t && i && arr[i * w - w + j - 1] < vall) maxl =  ((maxl > arr[i * w - w + j - 1]) ? (maxl) : (arr[i * w - w + j - 1]));
            if(b && i < h - 1 && arr[i * w + w + j - 1] < vall) maxl =  ((maxl > arr[i * w + w + j - 1]) ? (maxl) : (arr[i * w + w + j - 1]));
            wch += maxl == myVal;
        }
        if(j < w - 1 && r && myVal < arr[i * w + j + 1]) {
            int valr = arr[i * w + j + 1];
            int maxr = myVal;
            if(r > 1 && j < w - 2 && arr[i * w + j + 2] < valr) maxr =  ((maxr > arr[i * w + j + 2]) ? (maxr) : (arr[i * w + j + 2]));
            if(t && i && arr[i * w - w + j + 1] < valr) maxr =  ((maxr > arr[i * w - w + j + 1]) ? (maxr) : (arr[i * w - w + j + 1]));
            if(b && i < h - 1 && arr[i * w + w + j + 1] < valr) maxr =  ((maxr > arr[i * w + w + j + 1]) ? (maxr) : (arr[i * w + w + j + 1]));
            wch += maxr == myVal;
        }
        if(i && t && myVal < arr[i * w + j - w]) {
            int valt = arr[i * w + j - w];
            int maxt = myVal;
            if(t > 1 && i > 1 && arr[i * w + j - 2 * w] < valt) maxt =  ((maxt > arr[i * w + j - 2 * w]) ? (maxt) : (arr[i * w + j - 2 * w]));
            if(l && j && arr[i * w + j - w - 1] < valt) maxt =  ((maxt > arr[i * w + j - w - 1]) ? (maxt) : (arr[i * w + j - w - 1]));
            if(r && j + 1 < w && arr[i * w + j - w + 1] < valt) maxt =  ((maxt > arr[i * w + j - w + 1]) ? (maxt) : (arr[i * w + j - w + 1]));
            wch += maxt == myVal;
        }
        if(i + 1 < h && b && myVal < arr[i * w + j + w]) {
            int valb = arr[i * w + j + w];
            int maxb = myVal;
            if(b > 1 && i + 2 < h && arr[i * w + j + 2 * w] < valb) maxb =  ((maxb > arr[i * w + j + 2 * w]) ? (maxb) : (arr[i * w + j + 2 * w]));
            if(l && j && arr[i * w + j + w - 1] < valb) maxb =  ((maxb > arr[i * w + j + w - 1]) ? (maxb) : (arr[i * w + j + w - 1]));
            if(r && j + 1 < w && arr[i * w + j + w + 1] < valb) maxb =  ((maxb > arr[i * w + j + w + 1]) ? (maxb) : (arr[i * w + j + w + 1]));
            wch += maxb == myVal;
        }
        addHere[i * w + j][l][t][r][b] = wch != 1;
    }

    rep(i, 0, h) rep(j, 0, w) rep(l, 0, 3) rep(t, 0, 3) rep(r, 0, 3) rep(b, 0, 3) {
        prefSum[i * w + j][l][t][r][b] = prefSumCol[i * w + j][l][t][r][b] = prefSumRow[i * w + j][l][t][r][b] = addHere[i * w + j][l][t][r][b];
        if(i) prefSum[i * w + j][l][t][r][b] += prefSum[i * w + j - w][l][t][r][b], prefSumCol[i * w + j][l][t][r][b] += prefSumCol[i * w + j - w][l][t][r][b];
        if(j) prefSum[i * w + j][l][t][r][b] += prefSum[i * w + j - 1][l][t][r][b], prefSumRow[i * w + j][l][t][r][b] += prefSumRow[i * w + j - 1][l][t][r][b];
        if(i && j) prefSum[i * w + j][l][t][r][b] -= prefSum[i * w +  j- w - 1][l][t][r][b];
    }
   
    ll ans = 0;
    rep(t, 0, h) rep(b, t, h) {  
        vector<int> changes;
        rep(r, 0, w) {
            int myCnt = 0;
            int indexTR = t * w + r, indexBR = b * w + r;
            rep(mw, 1, min(r + 1, 4) + 1) {
                myCnt = 0;
                myCnt += addHere[indexTR][min(2, mw - 1)][0][0][min(2, b - t)];
                if(b - t > 1) myCnt += addHere[indexTR + w][min(2, mw - 1)][1][0][min(2, b - t - 1)];
                if(b - t > 3) myCnt += colSum(r, t + 2, b - 2, min(2, mw - 1), 2, 0, 2);
                if(b - t > 2) myCnt += addHere[indexBR - w][min(2, mw - 1)][2][0][1];
                if(b != t) myCnt += addHere[indexBR][min(2, mw - 1)][min(2, b - t)][0][0];
        
                if(r && mw > 1) {
                    r--;
                    indexTR--, indexBR--;
                    myCnt += addHere[indexTR][min(2, mw - 2)][0][1][min(2, b - t)];
                    if(b - t > 1) myCnt += addHere[indexTR + w][min(2, mw - 2)][1][1][min(2, b - t - 1)];
                    if(b - t > 3) myCnt += colSum(r, t + 2, b - 2, min(2, mw - 2), 2, 1, 2);
                    if(b - t > 2) myCnt += addHere[indexBR - w][min(2, mw - 2)][2][1][1];
                    if(b != t) myCnt += addHere[indexBR][min(2, mw - 2)][min(2, b - t)][1][0];
                    indexTR++, indexBR++;
                    r++;
                }
        
                if(r > 1 && mw > 2) {
                    r -= 2;
                    indexTR -= 2, indexBR -= 2;
                    myCnt += rowSum((4 - mw) * r, t, r, (mw - 3) * 2, 0, 2, min(2, b - t));
                    if(b - t > 1) myCnt += rowSum((4 - mw) * r, t + 1, r, (mw - 3) * 2, 1, 2, min(2, b - t - 1));
                    if(b - t > 3) myCnt += rectSum((4 - mw) * r, t + 2, r, b - 2, (mw - 3) * 2, 2, 2, 2);
                    if(b - t > 2) myCnt += rowSum((4 - mw) * r, b - 1, r, (mw - 3) * 2, 2, 2, 1);
                    if(b != t) myCnt += rowSum((4 - mw) * r, b, r, (mw - 3) * 2, min(2, b - t), 2, 0);
                    indexTR += 2, indexBR += 2;
                    r += 2;
                }
                
                if(mw != 4) {
                    ans += myCnt == 1;
                }
            }
    
            int myRem = 0;
    
            if(r > 2) {
                r -= 2;
                indexTR -= 2, indexBR -= 2;
    
                myRem -= rowSum(0, t, r, 2, 0, 2, min(2, b - t));
                if(b - t > 1) myRem -= rowSum(0, t + 1, r, 2, 1, 2, min(2, b - t - 1));
                if(b - t > 3) myRem -= rectSum(0, t + 2, r, b - 2, 2, 2, 2, 2);
                if(b - t > 2) myRem -= rowSum(0, b - 1, r, 2, 2, 2, 1);
                if(b - t > 0) myRem -= rowSum(0, b, r, 2, min(2, b - t), 2, 0);
    
                myRem += addHere[indexTR][1][0][2][min(2, b - t)];
                if(b - t > 1) myRem += addHere[indexTR + w][1][1][2][min(2, b - t - 1)];
                if(b - t > 3) myRem += colSum(r, t + 2, b - 2, 1, 2, 2, 2);
                if(b - t > 2) myRem += addHere[indexBR - w][1][2][2][1];
                if(b - t > 0) myRem += addHere[indexBR][1][min(2, b - t)][2][0];
    
                if(r) {
                    r--;
                    indexTR -= 1, indexBR -= 1;
                    myRem += addHere[indexTR][0][0][2][min(2, b - t)];
                    if(b - t > 1) myRem += addHere[indexTR + w][0][1][2][min(2, b - t - 1)];
                    if(b - t > 3) myRem += colSum(r, t + 2, b - 2, 0, 2, 2, 2);
                    if(b - t > 2) myRem += addHere[indexBR - w][0][2][2][1];
                    if(b - t > 0) myRem += addHere[indexBR][0][min(2, b - t)][2][0];
                    indexTR += 1, indexBR += 1;
                    r++;
                }
                changes.pb(myRem + maxn);
                cntMap[myRem + maxn]++;
                
                indexTR += 2, indexBR += 2;
                r += 2;
            }
    
            if(r + 1 >= 4) {
                ans += cntMap[1 - myCnt + maxn];
            }
    
    
        } 
        repIn(i, changes) cntMap[i] = 0;
        changes.clear();
    }

    cout << ans;

}

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