Submission #672982

#	Time	Username	Problem	Language	Result	Execution time	Memory
672982		viwlesxq	Trading (IZhO13_trading)	C++17	100 / 100	377 ms	20928 KiB

trading

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef string str;

#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()

 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	deque <pair <int, int>> l(m), r(m), x(m);
	for (int i = 0; i < m; i++) {
		cin >> l[i].F >> r[i].F >> x[i].F;
		l[i].F--, r[i].F--;
		l[i].S = i, r[i].S = i, x[i].S = l[i].F;
	}
	sort(all(l));
	multiset <int> st;
	multiset <pair <int, int>> R;
	int cur = l.front().F;
	while (!l.empty() && l.front().F == cur) {
		st.insert(x[l.front().S].F - cur);
		R.insert({r[l.front().S].F, r[l.front().S].S});
		l.ppf();
	}
	vector <int> ans(n, 0);
	ans[cur] = *st.rbegin() + cur;
	for (int pos = cur + 1; pos < n; pos++) {
		while (!l.empty() && l.front().F == pos) {
			st.insert(x[l.front().S].F - pos);
			R.insert({r[l.front().S].F, l.front().S});
			l.ppf();
		}
		while (!R.empty() && R.begin()->F == pos - 1) {
			auto it = st.find(x[R.begin()->S].F - x[R.begin()->S].S);
			st.erase(it);
			R.erase(R.begin());
		}
		if (!st.empty()) ans[pos] = *st.rbegin() + pos;
	}
	for (int i = 0; i < n; i++) cout << ans[i] << ' ';
}

• Subtask 1: 100 / 100