Submission #69332054

---

Source Code Expand

//# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#include"atcoder/all"
using namespace atcoder;
typedef modint998244353 mi;
using namespace std;
#define all(a) a.begin(),a.end()
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
#define compress(a) sort(all(a));a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
constexpr ll mod=1000000007;
constexpr ll inf=3e18;

const int T=10000001;
vector<int>event_in[T],event_out[T*2];

struct event{
	ll timeslice;
	int io;
	int id;
};

bool operator<(const event &lhs,const event &rhs){
	if(lhs.timeslice<rhs.timeslice)return true;
	if(lhs.timeslice>rhs.timeslice)return false;
	return lhs.io<rhs.io;
}
bool operator>(const event &lhs,const event &rhs){
	if(lhs.timeslice>rhs.timeslice)return true;
	if(lhs.timeslice<rhs.timeslice)return false;
	return lhs.io>rhs.io;
}

int main(){
	ll n,k;
	cin>>n>>k;
	vector<ll>a(n),b(n),c(n);
	rep(i,n)cin>>a[i]>>b[i]>>c[i];
	/*
	- 待ち行列から店に移動 2
	- 待ち行列に追加 1
	- 店から出る 0
	*/

	rep(i,n){
		event_in[a[i]].push_back(i);
	}
	vector<ll>ans(n);
	priority_queue<event,vector<event>,greater<event>>pq;
	queue<int>q;
	rep(i,n)pq.push({a[i],1,i});
	while(pq.size()){
		auto top=pq.top();
		//cout<<top.timeslice<<" "<<top.io<<" "<<top.id<<endl;
		pq.pop();
		if(top.io==0){
			k+=c[top.id];
		}
		else if(top.io==1){
			q.push(top.id);
		}
		while(q.size()){
			int v=q.front();
			if(k>=c[v]){
				k-=c[v];
				ans[v]=top.timeslice;
				pq.push({ans[v]+b[v],0,v});
				q.pop();
			}
			else break;
		}
	}


	rep(i,n){
		cout<<ans[i]<<endl;
	}

}

Submission Info

Judge Result