Submission #331823

#	Time	Username	Problem	Language	Result	Execution time	Memory
331823		AlexPop28	Restore Array (RMI19_restore)	C++11	100 / 100	537 ms	25220 KiB

restore

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

const int INF = (int)1e9 + 10;
    
struct Graph {
  int n;
  vector<bool> inq;
  vector<int> dist, cnt_push;
  vector<vector<pair<int, int>>> adj;
  
  Graph(int n_) : n(n_), inq(n), dist(n, INF), cnt_push(n), adj(n) {}

  void AddEdge(int from, int to, int cost) {
    adj[from].emplace_back(to, cost);
  }

  vector<int> Solve() {
    queue<int> q;
    q.emplace(0);
    dist[0] = 0;
    inq[0] = true;

    while (!q.empty()) {
      int node = q.front(); q.pop();

      for (auto &e : adj[node]) {
        int x, c; tie(x, c) = e;

        if (dist[node] + c < dist[x]) {
          dist[x] = dist[node] + c;
          if (++cnt_push[x] > n) {
            cout << "-1";
            exit(0);
          }

          q.emplace(x);
        }
      }
    }

    return dist;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, m; cin >> n >> m;
  Graph g(1 + n);
  for (int i = 0; i < m; ++i) {
    int l, r, k, val; cin >> l >> r >> k >> val; ++l, ++r;
    if (val == 0) {
      // at most r - l + 1 - k 1s
      k = r - l + 1 - k;
      // pref[r] - pref[l - 1] <= k
      // pref[r] <= pref[l - 1] + k
      g.AddEdge(l - 1, r, k);
    } else {
      // at least r - l + 1 - k + 1 1s
      k = r - l + 1 - k + 1;
      // pref[r] - pref[l - 1] >= k
      // pref[l - 1] <= pref[r] - k
      g.AddEdge(r, l - 1, -k);
    }
  }

  for (int i = 1; i <= n; ++i) {
    // pref[i] <= pref[i - 1] + 1
    g.AddEdge(i - 1, i, 1);
    // pref[i] >= pref[i - 1]
    g.AddEdge(i, i - 1, 0);
  }

  auto pref = g.Solve();
  for (int i = 1; i <= n; ++i) {
    cout << pref[i] - pref[i - 1] << " \n"[i == n];
  }
}

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