CSES - HIIT Open 2019 - Results
Submission details
Task:Final Array
Sender:bigint bugaa
Submission time:2019-05-25 11:38:15 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.10 sdetails
#2ACCEPTED0.07 sdetails
#3ACCEPTED0.01 sdetails

Code

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
using ll = long long;
const ll MOD = (int)1e9 + 7;

const int N = 1e5;
vector<pair<int, int>> ques[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b, x;
		cin >> a >> b >> x;
		--a; --b;
		ques[a].push_back({x-a, b});
	}

	priority_queue<pair<int, int>> que;
	for (int i = 0; i < n; ++i) {
		for (auto pr : ques[i]) {
			que.push(pr);
		}
		while((! que.empty()) && (que.top().second < i)) que.pop();

		int ans = -i;
		if (! que.empty()) ans = max(ans, que.top().first);
		cout << ans + i << ' ';
	}
	cout << '\n';
}

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 ...

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...

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