Submission #503585

#	Time	Username	Problem	Language	Result	Execution time	Memory
503585		lukameladze	Trading (IZhO13_trading)	C++14	100 / 100	295 ms	13304 KiB

trading

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 3e5 + 5;
int t,n,a[N],m,le,ri,x;
int lazy[4*N],tree[4*N];
void update(int node,int le,int ri,int start,int end,int val) {
	if(lazy[node]) {
		tree[node] = max(tree[node], lazy[node]);
		if(le!=ri) {
			lazy[2*node] = max(lazy[2*node],lazy[node]);
			lazy[2*node+1] = max(lazy[2*node + 1], lazy[node]);
		}
		lazy[node]=0;
	}
	if(le>end || ri<start) 
	return;
	if(start<=le && ri<=end) {
		tree[node] = max(tree[node],val);
		if(le != ri) {
			lazy[2*node] = max(lazy[2*node],val);
			lazy[2*node+1] = max(lazy[2*node + 1], val);
		}
		return;
	}
	int mid=(le+ri)/2;
	update(2*node,le,mid,start,end,val);
	update(2*node+1,mid+1,ri,start,end,val);
	tree[node]=max(tree[2*node],tree[2*node+1]);
}
int getans(int node,int le,int ri,int start,int end) {
	if(lazy[node]) {
		tree[node] = max(tree[node], lazy[node]);
		if(le!=ri) {
			lazy[2*node] = max(lazy[2*node],lazy[node]);
			lazy[2*node+1] = max(lazy[2*node + 1], lazy[node]);
		}
		lazy[node]=0;
	}
	if(le>end || ri<start) return -1e9;
	if(start<=le && ri<=end) {
		return tree[node];
	}
	int mid=(le+ri)/2;
	return max(getans(2*node,le,mid,start,end), getans(2*node+1,mid+1,ri,start,end));
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for (int i = 1; i <= m; i++) {
	    cin>>le>>ri>>x;
	    update(1,1,n,le,ri,x-le+300000);
	}
	for (int i = 1; i <= n; i++) {
	    cout<<max(0, getans(1,1,n,i,i) + i - 300000)<<" ";
	}
}

Compilation message (stderr)

trading.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main() {
      | ^~~~

• Subtask 1: 100 / 100