Submission #1286622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286622		mihai145	Restore Array (RMI19_restore)	C++20	100 / 100	493 ms	988 KiB

restore

#include <iostream>
#include <queue>
#include <vector>

int n, m;
std::vector<std::vector<std::pair<int, int>>> g;
std::vector<int> d;

inline void add_constraint(int a, int b, int k) {
  g[a].emplace_back(b, k);
  //  std::cout << "Add " << a << "---(" << k << ")--->" << b << '\n';
}

bool bellman_ford(int src) {
  std::vector<int> impr(n + 1, 0);
  std::vector<char> inq(n + 1, false);
  d[src] = 0;
  inq[src] = true;

  std::queue<int> q;
  q.push(src);

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inq[u] = false;

    for (auto e : g[u]) {
      int v = e.first;
      int new_cost = d[u] + e.second;

      if (new_cost < d[v]) {
        impr[v]++;

        if (impr[v] >= n) {
          return false;
        }

        d[v] = new_cost;
        if (inq[v]) {
          continue;
        }

        q.push(v);
        inq[v] = true;
      }
    }
  }

  return true;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::cin >> n >> m;

  g.resize(n + 1, std::vector<std::pair<int, int>>{});
  d.resize(n + 1, 1000000);

  for (int i = 1; i <= n; i++) {
    add_constraint(i - 1, i, 0);
    add_constraint(i, i - 1, 1);
  }

  for (int i = 0; i < m; i++) {
    int l, r, k, v;
    std::cin >> l >> r >> k >> v;
    ++l, ++r;

    // v = 0 -> >=k zeroes between l and r <=> <= r-l+1-k ones between l and r
    // v = 1 -> <k zeroes between l and r  <=> > r-l+1-k ones between l and r

    // v = 0 -> partsum(r) - partsum(l - 1) <= r-l+1-k
    // v = 1 -> partsum(r) - partsum(l - 1) > r-l+1-k <=> partsum(l - 1) -
    // partsum(r) < -r+l-1+k <=> partsum(l - 1) - partsum(r) <= -r+l-1+k-1

    if (v == 0) {
      add_constraint(r, l - 1, r - l + 1 - k);
    } else {
      add_constraint(l - 1, r, -r + l - 1 + k - 1);
    }
  }

  if (!bellman_ford(0)) {
    std::cout << -1 << '\n';
    return 0;
  }

  for (int i = 1; i <= n; i++) {
    std::cout << -(d[i] - d[i - 1]) << ' ';
  }
  std::cout << '\n';

  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55