#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 path_len[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;
path_len[0] = 1;
deque<int> q; q.eb(0); inq[0] = 1;
while(q.size()) {
int u = q.front(); q.of(); inq[u] = 0;
assert(0 <= u and u <= n);
for(ii e: g[u]) {
int v = e.fi, w = e.se;
assert(0 <= v and v <= n);
if(pref[v] > pref[u] + w) {
pref[v] = pref[u] + w;
path_len[v] = path_len[u] + 1;
if(path_len[v] > n) {
cout << -1;
return;
}
if(!inq[v]) {
if(q.empty() or pref[v] < pref[q.front()]) q.ef(v); // SLF optimization
else q.eb(v);
inq[v] = 1;
}
}
}
}
fori(i, 1, n) {
cout << pref[i] - pref[i - 1] << sp;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 7 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 8 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 2 |
Correct |
11 ms |
4044 KB |
Output is correct |
| 3 |
Correct |
11 ms |
4044 KB |
Output is correct |
| 4 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 5 |
Correct |
6 ms |
4044 KB |
Output is correct |
| 6 |
Correct |
5 ms |
4044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 2 |
Correct |
11 ms |
4044 KB |
Output is correct |
| 3 |
Correct |
11 ms |
4044 KB |
Output is correct |
| 4 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 5 |
Correct |
6 ms |
4044 KB |
Output is correct |
| 6 |
Correct |
5 ms |
4044 KB |
Output is correct |
| 7 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 8 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 9 |
Correct |
13 ms |
4084 KB |
Output is correct |
| 10 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 11 |
Correct |
5 ms |
4040 KB |
Output is correct |
| 12 |
Correct |
5 ms |
4044 KB |
Output is correct |
| 13 |
Correct |
10 ms |
4064 KB |
Output is correct |
| 14 |
Correct |
9 ms |
4044 KB |
Output is correct |
| 15 |
Correct |
16 ms |
4084 KB |
Output is correct |
| 16 |
Correct |
31 ms |
4084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 7 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 8 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 11 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 12 |
Correct |
11 ms |
4044 KB |
Output is correct |
| 13 |
Correct |
11 ms |
4044 KB |
Output is correct |
| 14 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 15 |
Correct |
6 ms |
4044 KB |
Output is correct |
| 16 |
Correct |
5 ms |
4044 KB |
Output is correct |
| 17 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 18 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 19 |
Correct |
13 ms |
4084 KB |
Output is correct |
| 20 |
Correct |
10 ms |
4044 KB |
Output is correct |
| 21 |
Correct |
5 ms |
4040 KB |
Output is correct |
| 22 |
Correct |
5 ms |
4044 KB |
Output is correct |
| 23 |
Correct |
10 ms |
4064 KB |
Output is correct |
| 24 |
Correct |
9 ms |
4044 KB |
Output is correct |
| 25 |
Correct |
16 ms |
4084 KB |
Output is correct |
| 26 |
Correct |
31 ms |
4084 KB |
Output is correct |
| 27 |
Correct |
6 ms |
4044 KB |
Output is correct |
| 28 |
Correct |
6 ms |
4044 KB |
Output is correct |
| 29 |
Correct |
7 ms |
4044 KB |
Output is correct |
| 30 |
Correct |
7 ms |
3968 KB |
Output is correct |
| 31 |
Correct |
7 ms |
4044 KB |
Output is correct |
| 32 |
Correct |
7 ms |
4044 KB |
Output is correct |
| 33 |
Correct |
6 ms |
4056 KB |
Output is correct |
| 34 |
Correct |
6 ms |
3916 KB |
Output is correct |
| 35 |
Correct |
7 ms |
4044 KB |
Output is correct |
| 36 |
Correct |
7 ms |
4044 KB |
Output is correct |
