Submission #1146629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146629		mannshah1211	Restore Array (RMI19_restore)	C++20	100 / 100	277 ms	1284 KiB

restore

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "deb.h"
#else
#define debug(...) 
#endif

const int inf = 1e9;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> g(n + 1);
  vector<tuple<int, int, int>> edges(m);
  for (int i = 0; i < n; i++) {
    // p[i + 1] - p[i] >= 0
    // p[i + 1] - p[i] <= 1
    g[i + 1].emplace_back(i, 0);
    g[i].emplace_back(i + 1, 1);
    edges.emplace_back(i + 1, i, 0);
    edges.emplace_back(i, i + 1, 1);
  }
  for (int i = 0; i < m; i++) {
    int l, r, k, v;
    cin >> l >> r >> k >> v;
    ++l; ++r;
    if (v == 0) {
      g[r].emplace_back(l - 1, -k);
      edges.emplace_back(r, l - 1, -k);
    } else {
      g[l - 1].emplace_back(r, k - 1);
      edges.emplace_back(l - 1, r, k - 1);
    }
  }
  vector<int> d(n + 1, inf);
  d[0] = 0;
  for (int i = 0; i < n + 2; i++) {
    for (auto [u, v, w] : edges) {
      d[v] = min(d[v], d[u] + w);
    }
  }
  bool neg = false;
  for (auto [u, v, w] : edges) {
    if (d[v] > d[u] + w) {
      neg = true;
    }
  }
  if (neg) {
    cout << -1 << '\n';
    return;
  }
  for (int i = 1; i <= n; i++) {
    cout << 1 - d[i] + d[i - 1] << " \n"[i == n];
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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