Submission #47527

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
47527	2018-05-05T02:34:20 Z	aome	Trading (IZhO13_trading)	C++17	100 / 100	457 ms	65536 KB

trading

#include <bits/stdc++.h>

using namespace std;

const int N = 300005;

int n, m;
int res[N];
int l[N], r[N], x[N];
set< pair<int, int> > s;
vector<int> vec[N];

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> l[i] >> r[i] >> x[i];
		vec[l[i]].push_back(i);
		vec[r[i] + 1].push_back(-i);
	}
	for (int i = 1; i <= n; ++i) {
		for (auto j : vec[i]) {
			if (j > 0) s.insert({x[j] - l[j], j});
			else s.erase({x[-j] - l[-j], -j});
		}
		if (s.size()) res[i] = (--s.end()) -> first + i;
		cout << res[i] << ' ';
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	7544 KB	Output is correct
2	Correct	6 ms	7660 KB	Output is correct
3	Correct	7 ms	7660 KB	Output is correct
4	Correct	7 ms	7792 KB	Output is correct
5	Correct	8 ms	7856 KB	Output is correct
6	Correct	9 ms	7956 KB	Output is correct
7	Correct	199 ms	19628 KB	Output is correct
8	Correct	233 ms	24636 KB	Output is correct
9	Correct	233 ms	28224 KB	Output is correct
10	Correct	259 ms	32372 KB	Output is correct
11	Correct	290 ms	37268 KB	Output is correct
12	Correct	350 ms	42916 KB	Output is correct
13	Correct	313 ms	45720 KB	Output is correct
14	Correct	326 ms	50348 KB	Output is correct
15	Correct	350 ms	56784 KB	Output is correct
16	Correct	364 ms	60268 KB	Output is correct
17	Correct	361 ms	65536 KB	Output is correct
18	Correct	457 ms	65536 KB	Output is correct
19	Correct	387 ms	65536 KB	Output is correct
20	Correct	434 ms	65536 KB	Output is correct