#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector < vector < int > > greater(n, vector < int > (n+1, 0));
vector < vector < int > > smaller(n, vector < int > (n+1, n));
for (int i = 0; i < m; i++)
{
int l, r, k, value;
cin >> l >> r >> k >> value;
r++;
int len = r-l;
if (value == 0)
smaller[l][r] = min(smaller[l][r], len - k);
else
greater[l][r] = max(greater[l][r], len - k + 1);
}
for (int i = 0; i < n; i++)
smaller[i][i+1] = min(smaller[i][i+1], 1);
/*
for (int i = 0; i < n; i++)
for (int j = i+1; j <= n; j++)
cerr << i << " -> " << j << " " << smaller[i][j] << " " << greater[i][j] << "\n";
*/
vector < int > mi(n+1, 0);
vector < int > ma(n+1, n);
ma[0] = 0;
for (int i = 0; i < n; i++)
{
int res = 0;
/*if (mi[i] > ma[i])
{
cout << -1 << "\n";
return 0;
}*/
for (int j = n; j > i; j--)
{
res = max(res, greater[i][j]);
mi[j] = max(mi[j], mi[i] + res);
ma[j] = min(ma[j], ma[i] + smaller[i][j]);
if (j != n);
ma[j] = min(ma[j], ma[j+1]);
res = max(res-1, 0);
}
if (res != 0)
{
cout << -1 << "\n";
return 0;
}
}
/*for (int i = 0; i < n; i++)
for (int j = i+1; j <= n; j++)
{
if (mi[j] > mi[i] + smaller[i][j])
{
cout << -1 << "\n";
return 0;
}
}*/
vector < int > res;
for (int i = 1; i <= n; i++)
{
if (mi[i] > ma[i])
{
cout << -1 << "\n";
return 0;
}
res.emplace_back(mi[i] - mi[i-1]);
//assert(res.back() == 1 || res.back() == 0);
}
for (auto x : res)
cout << x << " ";
cout << "\n";
return 0;
}
Compilation message
restore.cpp: In function 'int main()':
restore.cpp:48:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
48 | if (j != n);
| ^~
restore.cpp:49:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
49 | ma[j] = min(ma[j], ma[j+1]);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
195772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
195772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
