Submission #528301

#	Time	Username	Problem	Language	Result	Execution time	Memory
528301		doowey	Sandcastle 2 (JOI22_ho_t5)	C++14	100 / 100	1623 ms	2892 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

vector<vector<int>> A;
vector<vector<ll>> S4;
vector<vector<ll>> S5;
vector<vector<ll>> S6;
vector<vector<ll>> S7;
vector<vector<ll>> S8;

int n, m;

const int inf = 1e6;
int calc(int i, int j, int mode){
    vector<int> V;
    if(mode == 0){
        V = {A[i + 1][j], A[i][j+1]};
    }
    else if(mode == 1){
        V = {A[i + 1][j], A[i][j-1]};
    }
    else if(mode == 2){
        V = {A[i - 1][j], A[i][j+1]};
    }
    else if(mode == 3){
        V = {A[i - 1][j], A[i][j-1]};
    }
    else if(mode == 4){
        V = {A[i][j-1], A[i+1][j], A[i][j+1]};
    }
    else if(mode == 5){
        V = {A[i-1][j], A[i+1][j], A[i][j-1]};
    }
    else if(mode == 6){
        V = {A[i-1][j], A[i][j-1], A[i][j+1]};
    }
    else if(mode == 7){
        V = {A[i-1][j], A[i+1][j], A[i][j+1]};
    }
    else{
        V = {A[i-1][j], A[i+1][j], A[i][j+1],A[i][j-1]};
    }
    int maxi = 0;
    for(auto x : V){
        if(x < A[i][j]){
            maxi = max(maxi, x);
        }
    }

    int high = inf;
    for(auto x : V){
        if(x > A[i][j]){
            high = min(high, x);
        }
    }
    int cum = high - A[i][j];
    if(maxi == 0) cum += A[i][j];
    return cum;
}

unordered_map<ll, int> QR;

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    cin >> n >> m;
    bool swp = false;
    if(n > m){
        swp = true;
        swap(n, m);
    }
    A.resize(n);
    S4.resize(n);
    S5.resize(n);
    S6.resize(n);
    S7.resize(n);
    S8.resize(n);
    for(int i = 0 ; i < n; i ++ ){
        A[i].resize(m);
        S4[i].resize(m);
        S5[i].resize(m);
        S6[i].resize(m);
        S7[i].resize(m);
        S8[i].resize(m);
    }
    vector<int> C;
    if(swp == false){
        for(int i = 0 ; i < n; i ++ ){
            for(int j = 0 ; j < m ; j ++ ){
                cin >> A[i][j];
                C.push_back(A[i][j]);
            }
        }
    }
    else{
        for(int i = 0 ; i < m ; i ++ ){
            for(int j = 0 ; j < n; j ++ ){
                cin >> A[j][i];
                C.push_back(A[j][i]);
            }
        }
    }
    sort(C.begin(), C.end());
    C.resize(unique(C.begin(), C.end()) - C.begin());
    int id;
    for(int i = 0 ; i < n; i ++ ){
        for(int j = 0 ; j < m; j ++ ){
            A[i][j] = upper_bound(C.begin(), C.end(), A[i][j]) - C.begin();
        }
    }
    for(int i = 0; i < n; i ++ ){
        for(int j = 0; j < m; j ++ ){
            if(j > 0 && j + 1 < m && i + 1 < n)S4[i][j] = calc(i, j, 4);
            if(i > 0 && i + 1 < n && j > 0) S5[i][j] = calc(i, j, 5);
            if(i > 0 && j > 0 && j + 1 < m) S6[i][j] = calc(i, j, 6);
            if(j + 1 < m && i > 0 && i + 1 < n) S7[i][j] = calc(i, j, 7);
            if(i > 0 && j > 0 && i + 1 < n && j + 1 < m)S8[i][j] = calc(i, j, 8);
            if(i){
                S5[i][j] += S5[i-1][j];
                S7[i][j] += S7[i-1][j];
                S8[i][j] += S8[i-1][j];
            }
            if(j){
                S4[i][j] += S4[i][j-1];
                S6[i][j] += S6[i][j-1];
                S8[i][j] += S8[i][j-1];
            }
            if(i && j){
                S8[i][j] -= S8[i-1][j-1];
            }
        }
    }
    ll res = 0;
    res += n * m;
    for(int i = 0 ; i < n; i ++ ){
        for(int j = 0 ; j < m ; j ++ ){
            for(int k = j + 1 ; k < m ; k ++ ){
                if(A[i][k] > A[i][k - 1]){
                    break;
                }
                res ++ ;
            }
            for(int k = j - 1; k >= 0 ; k -- ){
                if(A[i][k] > A[i][k + 1]){
                    break;
                }
                res ++ ;
            }
            for(int k = i + 1; k < n; k ++ ){
                if(A[k][j] > A[k - 1][j]){
                    break;
                }
                res ++ ;
            }
            for(int k = i - 1; k >= 0; k -- ){
                if(A[k][j] > A[k + 1][j]){
                    break;
                }
                res ++ ;
            }
        }
    }
    ll add;
    int jj;
    for(int i = 0 ; i < n; i ++ ){
        for(int ii = i + 1; ii < n; ii ++ ){
            QR.clear();
            for(int j = 0; j < m; j ++ ){
                if(j > 0){
                    jj = j;
                    add = 0;
                    add += S8[ii-1][jj-1] - S8[i][jj-1];
                    add += calc(ii,jj,3);
                    add += calc(i,jj,1);
                    add += S4[i][jj-1];
                    add += S6[ii][jj-1];
                    add += S5[ii-1][jj]-S5[i][jj];
                    res += QR[inf-add];

                }
                if(j + 1 < m){
                    add = S8[i][j] - S8[ii-1][j];
                    add += calc(i,j,0);
                    add += calc(ii,j,2);
                    add -= S4[i][j];
                    add -= S6[ii][j];
                    add += S7[ii-1][j]-S7[i][j];

                    QR[add] ++ ;
                }
            }
        }
    }
    cout << res << "\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:114:9: warning: unused variable 'id' [-Wunused-variable]
  114 |     int id;
      |         ^~

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