Submission #685085

#	Time	Username	Problem	Language	Result	Execution time	Memory
685085		vovamr	Restore Array (RMI19_restore)	C++17	20 / 100	100 ms	924 KiB

restore

#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;
      |             ~~~~~~~~^~~

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