Submission #681552

#	Time	Username	Problem	Language	Result	Execution time	Memory
681552		peijar	Furniture (JOI20_furniture)	C++17	5 / 100	5043 ms	23952 KiB

furniture

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

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int INF = 1e18;

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbLig, nbCol;
  cin >> nbLig >> nbCol;
  vector<vector<int>> dateDel(nbLig, vector<int>(nbCol));
  for (int lig = 0; lig < nbLig; ++lig)
    for (int col = 0; col < nbCol; ++col) {
      int x;
      cin >> x;

      if (!x)
        dateDel[lig][col] = INF;
      else
        dateDel[lig][col] = 0;
    }

  int nbRequetes;
  cin >> nbRequetes;
  vector<pair<int, int>> queries(nbRequetes);
  for (auto &[r, c] : queries) {
    cin >> r >> c;
    --r, --c;
  }

  for (int i = 0; i < nbRequetes; ++i) {
    auto [r, c] = queries[i];
    dateDel[r][c] = i + 1;
  }

  auto canReach = [&](int minDate) {
    vector<vector<int>> dp(nbLig, vector<int>(nbCol));
    for (int lig = 0; lig < nbLig; ++lig)
      for (int col = 0; col < nbCol; ++col) {
        if (lig)
          dp[lig][col] |= dp[lig - 1][col];
        if (col)
          dp[lig][col] |= dp[lig][col - 1];
        if (!col and !lig)
          dp[lig][col] = 1;
        if (dateDel[lig][col] < minDate)
          dp[lig][col] = 0;
      }
    return dp[nbLig - 1][nbCol - 1];
  };

  while (true) {
    int lo = 1, up = nbRequetes + 1;
    while (lo < up) {
      int mid = (lo + up + 1) / 2;
      if (canReach(mid))
        lo = mid;
      else
        up = mid - 1;
    }
    dbg(lo);
    for (int i = 0; i < lo - 1; ++i) {
      auto [r, c] = queries[i];
      if (dateDel[r][c] != i + 1)
        continue;
      dateDel[r][c] = 0;
      dbg("DELETE", r, c);
    }
    if (lo == nbRequetes + 1)
      break;
    auto [r, c] = queries[lo - 1];
    dateDel[r][c] = INF;
    dbg("KEEP", r, c);
  }

  for (auto [r, c] : queries) {
    cout << (dateDel[r][c] == 0) << '\n';
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 95