#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int MAXN = 300005;
vector<vector<pair<ll, ll>>> beginr(MAXN), endr(MAXN);
/*pair<ll, ll> seg[4 * MAXN];
void push(int v)
{
seg[v * 2] = seg[v * 2 + 1] = seg[v];
lazy[v * 2] = lazy[v * 2 + 1] = lazy[v];
}
void update(int v, int tl, int tr, int l, int r, pair<ll, ll> change )
{
if(l > tr || r < tl)
return;
if(l == tl && r == tr)
{
if(seg[v] < change)
{
seg[v] = change;
lazy[v] = change;
}
return;
}
push(v);
int tm = (tl + tr) / 2;
update(2 * v, tl, min(tm, tr), l, min(tm, r), change);
update(2 * v + 1, max(tm + 1, tl), tr, max(l, tm + 1), r, change);
seg[v] = max(seg[v * 2], seg[v * 2 + 1]);
}
pair<ll, ll> get(int v, int tl, int tr, int pos)
{
if(tl == tr)
return seg[v];
}*/
int main()
{
ll n, m;
cin >> n >> m;
set<pair<ll, ll>> curr;
for (int i = 1; i <= m; i++)
{
pair<ll, ll> temp;
ll f, s, t;
cin >> f >> s >> t;
temp.first = t;
temp.second = f;
beginr[f].push_back(temp);
endr[s + 1].push_back(temp);
}
for (int day = 1; day <= n; day++)
{
for (pair<ll, ll> e : endr[day])
{
curr.erase({-e.first, e.second});
}
for (pair<ll, ll> e : beginr[day])
{
curr.insert({-e.first, e.second});
}
pair<ll, ll> maxi;
if (curr.size() > 0)
maxi = *(curr.begin());
else
maxi = {0, day};
// if (day == 5)
// cout << maxi.first << " " << maxi.second << "\n";
cout << -maxi.first + day - maxi.second << " ";
}
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
14408 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
