제출 #639884

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
639884		starchan	거래 (IZhO13_trading)	C++17	100 / 100	345 ms	26772 KiB

trading

#include<bits/stdc++.h>
using namespace std;
#define double long double
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+1
#define LMX (int)12e5+50
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
struct segment_tree
{
	vector<int> tree;
	vector<int> lazy;
	void init()
	{
		tree.assign(LMX, -INF);
		lazy.assign(LMX, -INF);
		return;
	}
	void push(int id)
	{
		tree[2*id] = max(tree[2*id], lazy[id]);
		tree[2*id+1] = max(tree[2*id+1], lazy[id]);
		lazy[2*id] = max(lazy[2*id], lazy[id]);
		lazy[2*id+1] = max(lazy[2*id+1], lazy[id]);
		lazy[id] = -INF;
		return;
	}
	void maximise(int val, int ql, int qr, int id, int l, int r)
	{
		if(r < ql || qr < l)
			return;
		if(ql <= l && r <= qr)
		{
			tree[id] = max(tree[id], val);
			lazy[id] = max(lazy[id], val);
			return;
		}
		int m = (l+r)/2;
		push(id);
		maximise(val, ql, qr, 2*id, l, m);
		maximise(val, ql, qr, 2*id+1, m+1, r);
		tree[id] = max(tree[2*id], tree[2*id+1]);
		return;
	}
	int point(int x, int id, int l, int r)
	{
		if(l==r)
			return tree[id];
		push(id);
		int m = (l+r)/2;
		if(x <= m)
			return point(x, 2*id, l, m);
		else
			return point(x, 2*id+1, m+1, r);
	}
};
signed main()
{
	fast();
	int n, q;
	cin >> n >> q;
	segment_tree work;
	work.init();
	while(q--)
	{
		int l, r, x;
		cin >> l >> r >> x;
		work.maximise(x-l, l, r, 1, 1, n);
	}
	for(int i = 1; i <= n; i++)
		cout << max(work.point(i, 1, 1, n)+i, 0ll) << " ";
	return 0;
}	

• Subtask 1: 100 / 100