제출 #685097

#제출 시각아이디문제언어결과실행 시간메모리
685097vovamrRestore Array (RMI19_restore)C++17
100 / 100
287 ms844 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("-O3") #pragma GCC optimize("unroll-loops") #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } const int N = 5e3 + 10; const int M = 2e4 + 100; array<int,3> edges[M]; int pm = 0; inline void solve() { int n, m; cin >> n >> m; for (int i = 0; i < m; ++i) { int l, r, k, x; cin >> l >> r >> k >> x; ++r; k = r - l - k; if (x == 1) { // pf[r] - pf[l] >= k // pf[l] <= pf[r] - k // gr[r].pb({l, -k - 1}); edges[pm++] = {r, l, -k - 1}; } else { // pf[r] - pf[l] <= k // pf[l] >= pf[r] + k // gr[l].pb({r, k}); edges[pm++] = {l, r, k}; } } for (int i = 0; i + 1 <= n; ++i) { // pf[i + 1] <= pf[i] + 1 // pf[i] >= pf[i + 1] - 1 // pf[i + 1] >= pf[i] edges[pm++] = {i, i + 1, 1}; edges[pm++] = {i + 1, i, 0}; // gr[i].pb({i + 1, 1}); // gr[i + 1].pb({i, 0}); } /* for (int i = 0; i <= n; ++i) { for (auto &[to, w] : gr[i]) { cout << "p[" << to << "] must be at most p[" << i << "] + " << w << '\n'; } } */ ve<int> d(n + 1, iinf); d[0] = 0; for (int it = 0; it <= n + 2; ++it) { bool ch = 0; for (int id = 0; id < pm; ++id) { const auto &[v, to, w] = edges[id]; if (d[v] != iinf && d[to] > d[v] + w) { d[to] = d[v] + w; ch = 1; } } if (it == n + 2 && ch) { return void(cout << -1); } if (!ch) break; } for (int id = 0; id < pm; ++id) { const auto &[i, to, w] = edges[id]; if (d[to] > d[i] + w || d[i] == iinf) { return void(cout << -1); } } for (int i = 0; i < n; ++i) { cout << d[i + 1] - d[i] << " "; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) solve(); cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...