输入样例:
2 6
5 5
1 1 5 3
2 2 2 6
3 1 2 3
4 1 6 1
5 1 3 3
6 1 3 4
输出样例:
2
-1
-1
1
-1
0
解析:
优先队列,排序规则为任务结束的时间,在新任务的时候,弹出已经结束的任务,并且恢复算力,然后进行判断即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,arr[N];
struct node{
int start,id,time,num;
bool operator<(const node& a)const{
return start+time>a.start+a.time;
}
};
priority_queue<node>q;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
for(int i=1;i<=m;i++){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
while(!q.empty()&&q.top().start+q.top().time<=a){
arr[q.top().id]+=q.top().num;
q.pop();
}
if(arr[b]<d){
printf("-1\n");
continue;
}
else{
arr[b]-=d;
q.push({a,b,c,d});
printf("%d\n",arr[b]);
}
}
return 0;
}