#include<bits/stdc++.h>
using namespace std;
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); i--)
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define ii pair<int, int>
#define pb push_back
#define pf push_front
#define em emplace
#define ef emplace_front
#define eb emplace_back
#define om pop
#define of pop_front
#define ob pop_back
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '
void solve();
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int test_num = 1;
fori(test, 1, test_num) {
solve();
}
}
#define int long long
const int maxn = 1e5 + 5, inf = LLONG_MAX / 100ll;
int n, m;
vector<pair<int, int> > g[maxn];
int pref[maxn];
bool inq[maxn];
int up_cnt[maxn];
void solve() {
cin >> n >> m;
fori(i, 1, n) {
g[i].eb(i - 1, 0);
g[i - 1].eb(i, 1);
}
fori(i, 1, m) {
int l, r, k, val;
cin >> l >> r >> k >> val; l++; r++;
if(val == 0) {
g[l - 1].eb(r, (r - l + 1) - k);
}
else {
g[r].eb(l - 1, -((r - l + 1) - k + 1));
}
}
fill(all(pref), inf);
pref[0] = 0;
queue<int> q; q.em(0); inq[0] = 1;
while(q.size()) {
int u = q.front(); q.pop(); inq[u] = 0;
assert(1 <= u and u <= n);
for(ii e: g[u]) {
int v = e.fi, w = e.se;
assert(1 <= v and v <= n);
if(pref[v] > pref[u] + w) {
pref[v] = pref[u] + w;
up_cnt[v]++;
if(up_cnt[v] > n or pref[v] < 0) {
cout << -1;
return;
}
if(!inq[v]) {
q.em(v);
inq[v] = 1;
}
}
}
}
fori(i, 1, n) {
cout << pref[i] - pref[i - 1] << sp;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
6752 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
7996 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
7996 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
6752 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
