#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;
}
ve<int> pf(n + 1);
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);
++pf[l], --pf[r + 1];
}
else if (k == r - l + 1 && !x) {
upd(0, 0, n - 1, l, r, 0);
++pf[l], --pf[r + 1];
}
}
for (int i = 1; i < n; ++i) pf[i] += pf[i - 1];
set<int> unused;
for (int i = 0; i < n; ++i) if (!pf[i]) {
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 - 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 - 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;
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
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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
468 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
28 ms |
548 KB |
Output is correct |
| 4 |
Correct |
25 ms |
564 KB |
Output is correct |
| 5 |
Correct |
93 ms |
544 KB |
Output is correct |
| 6 |
Correct |
47 ms |
468 KB |
Output is correct |
| 7 |
Correct |
18 ms |
468 KB |
Output is correct |
| 8 |
Correct |
16 ms |
468 KB |
Output is correct |
| 9 |
Correct |
87 ms |
552 KB |
Output is correct |
| 10 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
980 KB |
Output is correct |
| 2 |
Correct |
9 ms |
980 KB |
Output is correct |
| 3 |
Correct |
9 ms |
980 KB |
Output is correct |
| 4 |
Correct |
9 ms |
996 KB |
Output is correct |
| 5 |
Correct |
10 ms |
740 KB |
Output is correct |
| 6 |
Correct |
8 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
980 KB |
Output is correct |
| 2 |
Correct |
9 ms |
980 KB |
Output is correct |
| 3 |
Correct |
9 ms |
980 KB |
Output is correct |
| 4 |
Correct |
9 ms |
996 KB |
Output is correct |
| 5 |
Correct |
10 ms |
740 KB |
Output is correct |
| 6 |
Correct |
8 ms |
724 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
980 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
468 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
28 ms |
548 KB |
Output is correct |
| 4 |
Correct |
25 ms |
564 KB |
Output is correct |
| 5 |
Correct |
93 ms |
544 KB |
Output is correct |
| 6 |
Correct |
47 ms |
468 KB |
Output is correct |
| 7 |
Correct |
18 ms |
468 KB |
Output is correct |
| 8 |
Correct |
16 ms |
468 KB |
Output is correct |
| 9 |
Correct |
87 ms |
552 KB |
Output is correct |
| 10 |
Correct |
1 ms |
468 KB |
Output is correct |
| 11 |
Correct |
9 ms |
980 KB |
Output is correct |
| 12 |
Correct |
9 ms |
980 KB |
Output is correct |
| 13 |
Correct |
9 ms |
980 KB |
Output is correct |
| 14 |
Correct |
9 ms |
996 KB |
Output is correct |
| 15 |
Correct |
10 ms |
740 KB |
Output is correct |
| 16 |
Correct |
8 ms |
724 KB |
Output is correct |
| 17 |
Incorrect |
9 ms |
980 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
