제출 #1092534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1092534		May27_th	Restore Array (RMI19_restore)	C++17	0 / 100	85 ms	860 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 = 0; i <= N; i ++) {
    edges.pb({N + 1, i, 0});
  }
  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[N + 1] = 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 ++) {
    d[i] -= d[0];
    if (d[i] > d[i - 1]) cout << 0 << " ";
    else cout << 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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55