Submission #380346

#	Time	Username	Problem	Language	Result	Execution time	Memory
380346		ritul_kr_singh	Trading (IZhO13_trading)	C++17	100 / 100	446 ms	41172 KiB

trading

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

struct segtree{
	int sz = 1;
	vector<int> a;
	segtree(int n){
		while(sz < n) sz *= 2;
		a.assign(2*sz, -1e18);
	}
	void update(int i, int val, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = val);
		int mx = (lx+rx)/2;
		if(i<mx) update(i, val, 2*x+1, lx, mx);
		else update(i, val, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int val){ update(i, val, 0, 0, sz); }
	int get(){ return a[0]; }
};
 
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n, m; cin >> n >> m;
	int a[m], ans[n];
	vector<int> starts[n], ends[n];
	for(int i=0, l, r; i<m; ++i){
		cin >> l >> r >> a[i];
		starts[l-1].push_back(i);
		ends[r-1].push_back(i);
	}

	segtree st(m);

	for(int i=0; i<n; ++i){
		for(int j : starts[i]) st.update(j, a[j]-i);
		ans[i] = max(0LL, st.get()+i);
		for(int j : ends[i]) st.update(j, -1e18);
	}

	for(int i : ans) cout << i << ' ';
}

• Subtask 1: 100 / 100