제출 #344507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
344507		nandonathaniel	거래 (IZhO13_trading)	C++14	0 / 100	14 ms	14660 KiB

trading

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=300005;

vector<pii> masuk[MAXN];
vector<int> keluar[MAXN];

int tree[4*MAXN],lazy[4*MAXN];

void updatenode(int now,int val){
	tree[now]+=val;
	lazy[now]+=val;
}

void pushdown(int now){
	updatenode(2*now,lazy[now]);
	updatenode(2*now+1,lazy[now]);
	lazy[now]=0;
}

void update(int now,int L,int R,int x,int y,int val){
	if(L>=x && R<=y){
		updatenode(now,val);
		return;
	}
	if(L>y || R<x)return;
	int 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]);
}

int query(int now,int L,int R,int x,int y){
	if(L>=x && R<=y)return tree[now];
	if(L>y || R<x)return -2e9;
	int 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);
	int n,m,l,r,x;
	cin >> n >> m;
	for(int 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(int 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);
		int brp=query(1,1,m,1,m);
		if(brp<1)brp=0;
		cout << brp;
		if(i<n)cout << " ";
	}
	cout << '\n';
	return 0;
}

• Subtask 1: 0 / 100