제출 #1010664

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

trading

#include<bits/stdc++.h>
using namespace std;
const int maxn = 300007;
#define ll long long
ll n,m,k,a,b,c;
pair<ll,ll> val[maxn];
priority_queue<pair<ll,ll>> vre;
vector<pair<ll,ll>> zak;
int main(){
	
	cin>>n>>m;
	for(int i = 0; i<m; i++){
		cin>>a>>b>>c;
		if(val[a].first==0) val[a]={b,c};
		else{
			while(true){
				if(val[a].first!=0){
					if(val[a].second<c){
						int tr = val[a].first;
						int tpc = val[a].second;
						val[a] = {b,c};
						a=b+1;
						b=tr;
						c=tpc;
					}
					else{
						if(val[a].first<b){
							c+=val[a].first+1-1;
							a=val[a].first+1;
							
						}
						else break;
					}
				}
				else{
					val[a]={b,c};
					break;
				}
			}
		}
		
	}
	pair<ll,ll> tre;
	for(int i = 1; i<n+1; i++){
		bool ch = false;
		if(!vre.empty()){
			tre=vre.top();
			vre.pop();
			vre.push({tre.first+1,tre.second});
		}
		if(val[i].second!=0){
			vre.push({val[i].second,i});
		}
		while(!vre.empty() and val[vre.top().second].first<i){
			vre.pop();
			ch=true;
		}
		if(ch && !vre.empty()){
			zak.clear();
			int pok = vre.size();
			for(int j = 0; j<pok; j++){
				tre=vre.top();
				vre.pop();
				zak.push_back({tre.first+(i-tre.second),tre.second});
			}
			for(auto e: zak){
				vre.push(e);
			}
		}
		if (!vre.empty()) cout<<vre.top().first<<' ';
		else cout<<0<<' ';
	}
	return 0;
}

• Subtask 1: 0 / 100