제출 #645355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645355		Alex_tz307	Restore Array (RMI19_restore)	C++17	100 / 100	117 ms	1100 KiB

restore

#include <bits/stdc++.h>

using namespace std;

const int kN = 5e3;
const int INF = 1e9;
int n, m, d[1 + kN], cnt[1 + kN];
vector<pair<int, int>> g[1 + kN];
bitset<1 + kN> inQ;

/// Sistem de inecuatii diferentiale peste sumele partiale pe prefix
/// Dupa ce rezolv sistemul pentru sumele partiale obtin simplu si elementele: a[i] = p[i] - p[i - 1]

bool BellmanFord(int s) {
  for (int i = 0; i <= n; ++i) {
    d[i] = INF;
  }
  d[s] = 0;
  queue<int> q;
  q.emplace(s);
  inQ[s] = true;
  cnt[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inQ[u] = false;
    for (const auto &it : g[u]) {
      int v, w;
      tie(v, w) = it;
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        if (d[v] < 0) {
          return true;
        }
        if (!inQ[v]) {
          if (cnt[v] == n - 1) {
            return true;
          }
          q.emplace(v);
          inQ[v] = true;
          cnt[v] += 1;
        }
      }
    }
  }
  return false;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int l, r, k, v;
    cin >> l >> r >> k >> v;
    r += 1;
    if (v == 0) {
      /// sunt cel putin k valori de 0 in intervalul l..r <=> p[r] - p[l - 1] <= (r - l + 1) - k
      g[l].emplace_back(r, (r - l) - k);
    } else {
      /// sunt cel putin (r - l + 1) - k + 1 valori de in intervalul l..r
      /// <=> p[r] - p[l - 1] >= (r - l + 1) - k + 1 | *(-1)
      /// <=> p[l - 1] - p[r] <= -(r - l + 1) + k - 1
      g[r].emplace_back(l, -(r - l) + k - 1);
    }
  }
  for (int i = 1; i <= n; ++i) {
    /// p[i - 1] <= p[i] <= p[i - 1] + 1

    /// p[i - 1] - p[i] <= 0
    g[i].emplace_back(i - 1, 0);

    /// p[i] - p[i - 1] <= 1
    g[i - 1].emplace_back(i, 1);
  }
  if (BellmanFord(0)) {
    cout << "-1\n";
  } else {
    for (int i = 1; i <= n; ++i) {
      cout << d[i] - d[i - 1] << ' ';
    }
    cout << '\n';
  }
  return 0;
}

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