Submission #1092546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092546		May27_th	Restore Array (RMI19_restore)	C++17	100 / 100	447 ms	1308 KiB

restore

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
 
using namespace std;
 
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

const int MAXN = 2e5 + 10;
const i64 INF = 1e18;
void Solve(void) {  
  int N, M; cin >> N >> M;
  vector<array<int, 3>> edges;
  for (int i = 1; i <= N; i ++) {
    edges.pb({i, i - 1, 0});
    edges.pb({i - 1, i, 1});
  }
  for (int i = 0; i < M; i ++) {
    int l, r, k, v; cin >> l >> r >> k >> v;
    r ++;
    if (v == 0) edges.pb({r, l, -k});
    else edges.pb({l, r, k - 1});
  }
  // Add new vertex N + 1 to the graph -> cnt[i] = shortest path from N + 1 to i;
  vector<i64> d(N + 5, INF); d[0] = 0;
  int x = -1;
  for (int i = 0; i < N; i ++) {
    x = -1;
    for (auto [u, v, w] : edges) {
      // cout << u << " " << v << " " << w << "\n";
      if (d[u] < INF) {
        if (d[u] + w < d[v]) {
          x = v;
          d[v] = max(-INF, d[u] + w);
        }
      }
    }
  }

  if (x != -1) {
    cout << -1 << "\n";
    return;
  }
  for (int i = 1; i <= N; i ++) {
    // cout << d[i] << " ";
    cout << (d[i] > d[i - 1] ? 0 : 1) << " ";
  } 
}
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(10);
  int Tests = 1; // cin >> Tests; 
  while (Tests --) {
    Solve();    
  }
}

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