Submission #69337471

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace IO {
	template<typename T> inline void read(T &x) {
		bool f = 1;
		x = 0;
		char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-')f = 0;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
		x = f ? x : -x;
	}
	template<typename T> inline void write(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(('0' + x % 10));
	}
	template <typename T, typename ...Args> inline
	void read(T &x, Args &...args) {read(x),read(args...);}
	template<typename T> inline void write(T x, char c) {write(x), putchar(c);}
}
using namespace IO;
const int INF=1e18;

int n,k;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>n>>k;
	vector<int> a(n),b(n),c(n);
	for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];
	vector<int> ans(n,-1);
	queue<int> s;
	priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int> > > ss;
	int x=0,idx=0;
	while(idx<n||!s.empty()||!ss.empty())
	{
		int t=min((idx<n?a[idx]:INF),(!ss.empty()?ss.top().first:INF));
		if(t==INF) break;
		while(!ss.empty()&&ss.top().first==t)
		{
			x-=c[ss.top().second];
			ss.pop();
		}
		while(idx<n&&a[idx]==t)
		{
			s.push(idx);
			++idx;
		}
		while(!s.empty())
		{
			int sum=s.front();
			if(x+c[sum]<=k)
			{
				s.pop();
				ans[sum]=t;
				x+=c[sum];
				ss.emplace(b[sum]+t,sum);
			}
			else break;
		}
	}
	for(int i=0;i<n;i++) cout<<ans[i]<<endl;
	
	return 0;
}

Submission Info

Judge Result