CSES - HIIT Open 2019 - Results
 Task: Final Array Sender: .* Submission time: 2019-05-25 15:20:45 +0300 Language: C++ Status: READY Result: ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.17 sdetails
#2ACCEPTED0.11 sdetails
#3ACCEPTED0.02 sdetails

### Code

```#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define M 1000000007
#define N (1<<18)
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

int n, m, a, b, x;
vector<pair<int,int>> alk, pat;
multiset<int> st;

int main() {
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
cin >> n >> m;
for(int i=0; i<m; i++) {
cin >> a >> b >> x;
int nx = x-a;
alk.push_back(make_pair(a, nx));
pat.push_back(make_pair(b, nx));
}
sort(alk.begin(), alk.end());
sort(pat.begin(), pat.end());
auto p1 = alk.begin();
auto p2 = pat.begin();
for(int i=1; i<=n; i++) {
while(p1 != alk.end() && p1->first == i) {
st.insert(p1->second);
p1++;
}
if(st.size() == 0)
cout << 0 << " ";
else
cout << (*prev(st.end(), 1))+i<< " ";
while(p2 != pat.end() && p2->first == i) {
st.erase(st.find(p2->second));
p2++;
}
}
}
```

### Test details

#### Test 1

Verdict: ACCEPTED

input
100000 100000
29706 39977 913671103
20575 89990 878449866
1691 70785 229168045
81099 81323 611730238
...

correct output
227121122 450258482 450258483 ...

user output
227121122 450258482 450258483 ...
Truncated

#### Test 2

Verdict: ACCEPTED

input
100000 100000
1 100000 1
1 100000 2
1 100000 3
1 100000 4
...

correct output
100000 100001 100002 100003 10...

user output
100000 100001 100002 100003 10...
Truncated

#### Test 3

Verdict: ACCEPTED

input
8 2
1 4 1
1 8 1

correct output
1 2 3 4 5 6 7 8

user output
1 2 3 4 5 6 7 8