Submission #331819

#	Time	Username	Problem	Language	Result	Execution time	Memory
331819		AlexPop28	Restore Array (RMI19_restore)	C++11	0 / 100	1097 ms	131792 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 {
  vector<bool> inq;
  vector<int> dist, q;
  vector<vector<pair<int, int>>> adj;
  
  Graph(int n) : inq(n), dist(n, INF), adj(n) {}

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

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

    for (int it = 0; it < (int)q.size(); ++it) {
      int node = q[it];
      inq[node] = false;

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

        if (dist[node] + c < dist[x]) {
          dist[x] = dist[node] + c;
          if (!inq[x]) {
            inq[x] = true;
            q.emplace_back(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 k 1s
      // 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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55