Submission #1111138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111138		fryingduc	Restore Array (RMI19_restore)	C++17	100 / 100	150 ms	1296 KiB

restore

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 5005;
int n, q;

int f[maxn];

struct info {
  int u, v, w;
};
vector<info> edges;
void solve() {
  cin >> n >> q;
  for(int i = 1; i <= n; ++i) {
    edges.push_back({i, i - 1, 1});
    edges.push_back({i - 1, i, 0});
  } 
  for(int i = 1; i <= q; ++i) {
    int l, r, k, v; cin >> l >> r >> k >> v;
    if(!v) {
      // at least k zeros
      edges.push_back({l, r + 1, -k});
    }
    else {
      // at most k - 1 zeros
      edges.push_back({r + 1, l, k - 1});
    }
  }
  memset(f, 0x3f, sizeof(f));
  f[0] = 0;
  // check neg cycle
  for(int ite = 1; ite <= n; ++ite) {
    for(auto i:edges) {
      int u = i.u, v = i.v;
      int w = i.w;
      f[u] = min(f[u], f[v] + w);
    }
  }
  for(auto i:edges) {
    if(f[i.u] > f[i.v] + i.w) {
      cout << -1;
      return;
    }
  }
  for(int i = 1; i <= n; ++i) {
    cout << (f[i] - f[i - 1] ? 0 : 1) << ' ';
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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