Submission #751581

#	Time	Username	Problem	Language	Result	Execution time	Memory
751581		tch1cherin	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	3176 ms	102780 KiB

joioi

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

void solve() {
  int H, W;
  cin >> H >> W;
  vector<vector<int>> A(H, vector<int>(W));
  vector<pair<int, int>> P;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      P.emplace_back(i, j);
      cin >> A[i][j];
    } 
  }
  int ans = INT_MAX;
  for (int r = 0; r < 2; r++) {
    sort(P.begin(), P.end(), [&](pair<int, int> x, pair<int, int> y) {
      return A[x.first][x.second] < A[y.first][y.second];
    });
    vector<vector<int>> x(H, vector<int>(W + 1));
    for (int i = 0; i < H; i++) {
      x[i][W] = INT_MAX;
      for (int j = W - 1; j >= 0; j--) {
        x[i][j] = min(x[i][j + 1], A[i][j]);
      }
    }
    multiset<int> Spref, Ssuff;
    for (int i = 0; i < H; i++) {
      Spref.insert(x[i][0]);
      Ssuff.insert(x[i][0]);
    }
    vector<int> height(H), pref(H), suff(H);
    vector<vector<bool>> used(H, vector<bool>(W, false));
    ans = min(ans, A[P.back().first][P.back().second] - A[P[0].first][P[0].second]);
    for (int i = 0; i < H * W - 1; i++) {
      auto [u, v] = P[i];    
      used[u][v] = true;
      for (int j = height[u]; j < W; j++) {
        if (!used[u][j]) {
          break;
        }
        height[u]++;
      }
      int p = u == 0 ? INT_MAX : pref[u - 1];
      for (int j = u; j < H; j++) {
        p = min(p, height[j]);
        if (pref[j] == p) {
          break;
        }
        Spref.erase(Spref.find(x[j][pref[j]]));
        pref[j] = p;
        Spref.insert(x[j][pref[j]]);
      }
      int s = u == H - 1 ? INT_MAX : suff[u + 1];
      for (int j = u; j >= 0; j--) {
        s = min(s, height[j]);
        if (suff[j] == s) {
          break;
        }
        Ssuff.erase(Ssuff.find(x[j][suff[j]]));
        suff[j] = s;
        Ssuff.insert(x[j][suff[j]]);
      }
      ans = min(ans, max(A[u][v] - A[P[0].first][P[0].second], A[P.back().first][P.back().second] - max(*Spref.begin(), *Ssuff.begin())));
    }
    for (int i = 0; i < H; i++) {
      reverse(A[i].begin(), A[i].end());
    }
  }
  cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40