Submission #685085

#TimeUsernameProblemLanguageResultExecution timeMemory
685085vovamrRestore Array (RMI19_restore)C++17
20 / 100
100 ms924 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #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; struct node { int s; int mn, cmn; node(int x = -1) : s(x) { mn = x, cmn = 1; } } t[4 * N]; int p[4 * N]; inline node mg(const node &a, const node &b) { node res; res.s = a.s + b.s; res.mn = min(a.mn, b.mn); res.cmn = (a.mn == res.mn ? a.cmn : 0) + (b.mn == res.mn ? b.cmn : 0); return res; } inline void mg(int v) { t[v] = mg(t[2 * v + 1], t[2 * v + 2]); } inline void apply(int v, int vl, int vr, int p) { t[v].mn = p, t[v].cmn = vr - vl + 1; t[v].s = (vr - vl + 1) * p; } inline void push(int v, int vl, int vr) { if (!~p[v]) return; int m = vl + vr >> 1; p[2 * v + 1] = p[v]; apply(2 * v + 1, vl, m, p[v]); p[2 * v + 2] = p[v]; apply(2 * v + 2, m + 1, vr, p[v]); p[v] = -1; } inline void build(int v, int vl, int vr) { if (vl == vr) return void(t[v] = node(-1)); int m = vl + vr >> 1; build(2 * v + 1, vl, m); build(2 * v + 2, m + 1, vr); mg(v); } inline void upd(int v, int vl, int vr, int l, int r, int x) { if (l > r) return; else if (vl == l && vr == r) { p[v] = x; apply(v, vl, vr, x); return; } push(v, vl, vr); int m = vl + vr >> 1; upd(2 * v + 1, vl, m, l, min(r, m), x); upd(2 * v + 2, m + 1, vr, max(l, m + 1), r, x); mg(v); } inline node get(int v, int vl, int vr, int l, int r) { if (vl == l && vr == r) return t[v]; push(v, vl, vr); int m = vl + vr >> 1; if (r <= m) return get(2 * v + 1, vl, m, l, r); else if (l > m) return get(2 * v + 2, m + 1, vr, l, r); else return mg(get(2*v+1,vl,m,l,m),get(2*v+2,m+1,vr,m+1,r)); } inline void solve() { int n, m; cin >> n >> m; ve<array<int,4>> e(m); for (auto &[l, r, k, x] : e) cin >> l >> r >> k >> x; sort(all(e)); if (n <= 18) { ve<int> pf(n); for (int ma = 0; ma < (1 << n); ++ma) { for (int i = 0; i < n; ++i) { pf[i] = ma >> i & 1 ^ 1; if (i) pf[i] += pf[i - 1]; } bool ok = 1; for (auto &[l, r, k, x] : e) { int s = pf[r] - (!l ? 0 : pf[l - 1]); ok &= (x == (s >= k ? 0 : 1)); } if (ok) { for (int i = 0; i < n; ++i) { cout << !(pf[i] - (!i ? 0 : pf[i - 1])) << " "; } return; } } cout << -1; return; } build(0, 0, n - 1); for (auto &[l, r, k, x] : e) { if (k == 1 && x == 1) { upd(0, 0, n - 1, l, r, 1); } else if (k == r - l + 1 && !x) { upd(0, 0, n - 1, l, r, 0); } } set<int> unused; for (int i = 0; i < n; ++i) if (get(0, 0, n - 1, i, i).mn == -1) { unused.insert(i); } bool ok = 1; for (auto &[l, r, k, x] : e) { auto c = get(0, 0, n - 1, l, r); auto [s, mn, cmn] = c; if (mn == -1) s -= mn * cmn; s = r - l + 1 - cmn * (mn == -1) - s; if (k == 1 && x == 0) { if (s > 0) continue; auto it = unused.lower_bound(l); if (it != unused.end() && *it <= r) { int p = *it; unused.erase(it); upd(0, 0, n - 1, p, p, 0); } } else if (k == r - l + 1 && x == 1) { s = r - l + 1 - cmn * (mn == -1) - s; if (s > 0) continue; auto it = unused.lower_bound(l); if (it != unused.end() && *it <= r) { int p = *it; unused.erase(it); upd(0, 0, n - 1, p, p, 1); } } } for (auto &x : unused) upd(0, 0, n - 1, x, x, 0); for (auto &[l, r, k, x] : e) { auto c = get(0, 0, n - 1, l, r); auto [s, mn, cmn] = c; assert(mn != -1); s = r - l + 1 - s; ok &= (x == (s >= k ? 0 : 1)); } if (!ok) return void(cout << -1); for (int i = 0; i < n; ++i) cout << get(0, 0, n - 1, i, i).s << " "; } 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; }

Compilation message (stderr)

restore.cpp: In function 'void push(int, int, int)':
restore.cpp:45:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  int m = vl + vr >> 1;
      |          ~~~^~~~
restore.cpp: In function 'void build(int, int, int)':
restore.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |  int m = vl + vr >> 1;
      |          ~~~^~~~
restore.cpp: In function 'void upd(int, int, int, int, int, int)':
restore.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |  int m = vl + vr >> 1;
      |          ~~~^~~~
restore.cpp: In function 'node get(int, int, int, int, int)':
restore.cpp:73:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |  int m = vl + vr >> 1;
      |          ~~~^~~~
restore.cpp: In function 'void solve()':
restore.cpp:91:21: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   91 |     pf[i] = ma >> i & 1 ^ 1;
      |             ~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...