Submission #170432

#	Time	Username	Problem	Language	Result	Execution time	Memory
170432		div2der	Trading (IZhO13_trading)	C++14	100 / 100	865 ms	25328 KiB

trading

#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 / 100