Submission #344512

#	Time	Username	Problem	Language	Result	Execution time	Memory
344512		nandonathaniel	Trading (IZhO13_trading)	C++14	100 / 100	742 ms	44640 KiB

trading

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const LL MAXN=300005;
 
vector<pii> masuk[MAXN];
vector<LL> keluar[MAXN];
 
LL tree[4*MAXN],lazy[4*MAXN];
 
void updatenode(LL now,LL val){
	tree[now]+=val;
	lazy[now]+=val;
}
 
void pushdown(LL now){
	updatenode(2*now,lazy[now]);
	updatenode(2*now+1,lazy[now]);
	lazy[now]=0;
}
 
void update(LL now,LL L,LL R,LL x,LL y,LL val){
	if(L>=x && R<=y){
		updatenode(now,val);
		return;
	}
	if(L>y || R<x)return;
	LL mid=(L+R)/2;
	pushdown(now);
	update(2*now,L,mid,x,y,val);
	update(2*now+1,mid+1,R,x,y,val);
	tree[now]=max(tree[2*now],tree[2*now+1]);
}
 
LL query(LL now,LL L,LL R,LL x,LL y){
	if(L>=x && R<=y)return tree[now];
	if(L>y || R<x)return -2e9;
	LL mid=(L+R)/2;
	pushdown(now);
	return max(query(2*now,L,mid,x,y),query(2*now+1,mid+1,R,x,y));
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	LL n,m,l,r,x;
	cin >> n >> m;
	for(LL i=1;i<=m;i++){
		cin >> l >> r >> x;
		masuk[l].push_back({i,x});
		keluar[r+1].push_back(i);
		update(1,1,m,i,i,-2e9);
	}
	for(LL i=1;i<=n;i++){
		for(auto isi : keluar[i])update(1,1,m,isi,isi,-2e9);
		for(auto isi : masuk[i])update(1,1,m,isi.first,isi.first,2e9-i+isi.second);
		update(1,1,m,1,m,1);
		LL brp=query(1,1,m,1,m);
		if(brp<1)brp=0;
		cout << brp;
		if(i<n)cout << " ";
	}
	cout << '\n';
	return 0;
}

• Subtask 1: 100 / 100