oj.uz

Submission #681552

# Submission time Handle Problem Language Result Execution time Memory
681552 2023-01-13T10:01:59 Z peijar Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 23952 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 59 ms 468 KB Output is correct
3 Correct 55 ms 536 KB Output is correct
4 Correct 186 ms 636 KB Output is correct
5 Correct 210 ms 664 KB Output is correct
6 Correct 238 ms 724 KB Output is correct
7 Correct 202 ms 724 KB Output is correct
8 Correct 195 ms 724 KB Output is correct
9 Correct 191 ms 728 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 59 ms 468 KB Output is correct
3 Correct 55 ms 536 KB Output is correct
4 Correct 186 ms 636 KB Output is correct
5 Correct 210 ms 664 KB Output is correct
6 Correct 238 ms 724 KB Output is correct
7 Correct 202 ms 724 KB Output is correct
8 Correct 195 ms 724 KB Output is correct
9 Correct 191 ms 728 KB Output is correct
10 Correct 3308 ms 2132 KB Output is correct
11 Correct 136 ms 612 KB Output is correct
12 Execution timed out 5043 ms 23952 KB Time limit exceeded
13 Halted 0 ms 0 KB -