记录编号	605643	评测结果	AAAAA
题目名称	284.[NOI 1999]内存分配	最终得分	100
用户昵称	秋_Water	是否通过	通过
代码语言	C++	运行时间	0.217 s
提交时间	2025-09-05 20:07:12	内存使用	3.70 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
struct node{
	int m,p;
};
queue<node>q;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>qp;
set<pair<int,int>>s;
int n,m,t,p,cnt,ans;
bool insert(int t,int m,int p){
	for(auto it=s.begin();it!=s.end();it++){
		auto nt=next(it);
		int idst=it->first,ided=it->second,nxst=nt->first;
		if(nt!=s.end()&&nxst-(idst+ided)>=m){
			s.insert({idst+ided,m});
			qp.push({t+p,idst+ided});
			return 1;
		}
	}
	return 0;
}
void free(int x){
	while(!qp.empty()&&x>=qp.top().first){
		int tmp=qp.top().first;
		ans=tmp;
		while(!qp.empty()&&qp.top().first==tmp){
			pair<int,int>now=qp.top();
			qp.pop();
			s.erase(s.lower_bound({now.second,0}));
		}
		while(!q.empty()){
			node now=q.front();
			if(insert(tmp,now.m,now.p)){
				q.pop();
			}
			else{
				break;
			}
		}
	}
}
int main(){
	cin>>n;
	s.insert({-1,1});
	s.insert({n,1});
	while(cin>>t>>m>>p){
		if(t==0&&m==0&&p==0){
			break;
		}
		free(t);
		if(!insert(t,m,p)){
			q.push({m,p});
			cnt++;
		}
	}
	free(1e9+7);
	cout<<ans<<"\n"<<cnt;	
	
	return 0;
}