#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, 0, n) {
if(i >= 1) {
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;
deque<int> q; q.eb(0); inq[0] = 1;
int sum_dis = 0;
while(q.size()) {
while(pref[q.front()] * q.size() > sum_dis) {
q.push_back(q.front());
q.pop_front();
}
int u = q.front(); q.of(); inq[u] = 0; sum_dis -= pref[u];
for(ii e: g[u]) {
int v = e.fi, w = e.se;
if(pref[v] > pref[u] + w) {
pref[v] = pref[u] + w;
up_cnt[v]++;
if(up_cnt[v] > n) {
cout << -1;
return;
}
if(!inq[v]) {
if(q.empty() or pref[v] < pref[q.front()]) q.ef(v);
else q.eb(v);
inq[v] = 1;
sum_dis += pref[u];
}
}
}
}
fori(i, 1, n) {
cout << pref[i] - pref[i - 1] << sp;
}
}
Compilation message
restore.cpp: In function 'void solve()':
restore.cpp:59:36: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
59 | while(pref[q.front()] * q.size() > sum_dis) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1063 ms |
3404 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
3916 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
3916 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1063 ms |
3404 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
