Submission #528299

#TimeUsernameProblemLanguageResultExecution timeMemory
528299dooweySandcastle 2 (JOI22_ho_t5)C++14
80 / 100
5040 ms17072 KiB
#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; 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; for(int i = 0 ; i < n; i ++ ){ for(int j = 0 ; j < m ; j ++ ){ cin >> A[i][j]; C.push_back(A[i][j]); } } 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:99:9: warning: unused variable 'id' [-Wunused-variable]
   99 |     int id;
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...