Submission #739434

#	Time	Username	Problem	Language	Result	Execution time	Memory
739434		MODDI	Trading (IZhO13_trading)	C++14	100 / 100	448 ms	33440 KiB

trading

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m;
vector<pll> v[300100];
multiset<ll> st;
int main(){
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		ll l, r, d;
		cin>>l>>r>>d;
		v[l].pb(mp(1, d-l));
		v[r+1].pb(mp(0, d-l));
	}
	int ans[n+1];
	for(int i = 1; i <= n; i++){
		sort(v[i].begin(), v[i].end());
		for(auto t : v[i]){
			if(t.first == 1)	st.insert(t.second);
			else	st.erase(st.find(t.second));
		}
		if(st.size()==0)	ans[i] = 0;
		else ans[i] = *st.rbegin() + i;
	}
	for(int i = 1; i <= n; i++)
		cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}

• Subtask 1: 100 / 100