oj.uz

Submission #170432

# Submission time Handle Problem Language Result Execution time Memory
170432 2019-12-25T09:34:24 Z div2der Trading (IZhO13_trading) C++14
100 / 100
 865 ms 25328 KB 
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

#define sz(s) (int)(s.size())
#define eb emplace_back
#define mkp make_pair
#define all(x) x.begin(), x.end()

const int N = 3e5 + 500;
const int NN = 4e3;

int a[N];

vector <int> v[N];

set <pair <int, int>> st;

int x[N], l[N], r[N];

void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++ i) {
		cin >> l[i] >> r[i] >> x[i];
		v[l[i]].eb(i);
		int pos = -i;
		v[r[i] + 1].eb(pos);
	}
	/*for (int i = 1; i <= n; ++ i) {
		cerr << i << ": ";
		for (auto to : v[i])
			cerr << to << " ";
		cerr << '\n';
	}*/
	for (int i = 1; i <= n; ++ i) {
		int res = 0;
		for (auto to : v[i]) {
			int dif = x[to] - l[to];
			int pos = -to;
			int dif2 = x[pos] - l[pos];
			if (to <= 0)
				st.erase(mkp(dif2, pos));
			if (to >= 1)
				st.insert(mkp(dif, to));
		}
		if (!st.empty()) {
			res = (--st.end()) -> first + i;
		}
		cout << res << " ";
	}
}

int main () {
	solve();
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 11 ms 7492 KB Output is correct
6 Correct 14 ms 7672 KB Output is correct
7 Correct 404 ms 15956 KB Output is correct
8 Correct 444 ms 17560 KB Output is correct
9 Correct 460 ms 18036 KB Output is correct
10 Correct 526 ms 18508 KB Output is correct
11 Correct 516 ms 19184 KB Output is correct
12 Correct 584 ms 21044 KB Output is correct
13 Correct 580 ms 19688 KB Output is correct
14 Correct 616 ms 20500 KB Output is correct
15 Correct 685 ms 21872 KB Output is correct
16 Correct 717 ms 20524 KB Output is correct
17 Correct 689 ms 21580 KB Output is correct
18 Correct 744 ms 25328 KB Output is correct
19 Correct 722 ms 21752 KB Output is correct
20 Correct 865 ms 23880 KB Output is correct