Submission #1188299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188299		altern23	Trading (IZhO13_trading)	C++20	100 / 100	191 ms	33832 KiB

trading

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 5e5;
const ll INF = 4e18;
const int MOD = 998244353;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;		
	for(;tc--;){
		ll N, M; cin >> N >> M;
		vector<pii> in[N + 5], out[N + 5];
		for(int i = 1; i <= M; i++){
			ll l, r, x; cin >> l >> r >> x;
			in[l].push_back({x, l}), out[r + 1].push_back({x, l});
		}
		
		multiset<ll> ms;
		for(int i = 1; i <= N; i++){
			for(auto x : in[i]){
				ll val = x.fi, idx = x.sec;
				ms.insert(val - idx);
			}
			for(auto x : out[i]){
				ll val = x.fi, idx = x.sec;
				ms.erase(ms.find(val - idx));
			}
			if(!ms.empty()) cout << (*ms.rbegin()) + i << " ";
			else cout << 0 << " ";
		}
		cout << "\n";
	}
}

/*
7
5 3 1 7 4 6 4
*/

• Subtask 1: 100 / 100