Submission #672889

#	Time	Username	Problem	Language	Result	Execution time	Memory
672889		MilosMilutinovic	Restore Array (RMI19_restore)	C++14	100 / 100	355 ms	1044 KiB

restore

/**
 *    author:  wxhtzdy
 *    created: 18.12.2022 21:11:23
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int>> q;
  for (int i = 0; i < m; i++) {
    int l, r, k, v;
    cin >> l >> r >> k >> v;
    r += 1;
    int len = r - l;
    if (v == 0) {
      q.emplace_back(l, r, len - k);
    }
    if (v == 1) {
      q.emplace_back(r, l, -(len - k + 1));
    }
  }
  for (int i = 0; i < n; i++) {
    q.emplace_back(i, i + 1, 1);
    q.emplace_back(i + 1, i, 0);
  }
  const long long inf = (long long) 1e18;
  vector<long long> d(n + 1, inf);
  d[0] = 0;
  for (int iter = 0; iter <= n + 2; iter++) {
    bool any = false;
    for (auto& p : q) {
      int i = get<0>(p);
      int j = get<1>(p);
      int w = get<2>(p);
      if (d[i] < inf && d[j] > d[i] + w) {
        d[j] = max(-inf, d[i] + w);          
        any = true;
      }
    }
    if (iter == n + 2 && any) {
      cout << -1;
      return 0;
    }
  }
  long long prv = 0;
  for (int i = 1; i <= n; i++) {
    cout << d[i] - prv << " ";
    prv = d[i];
  }
  return 0;
}

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