AcWing 503. 借教室
原题链接
简单
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
long long r[1000010],a[1000010];
int d[1000010],s[1000010],t[1000010];
bool cheke(int mid,int n)
{
memset(a,0,sizeof a);
for(int i=1;i<=mid;i++)
{
a[s[i]]+=d[i];
a[t[i]+1]-=d[i];
}
for(int i=1;i<=n;i++)
{
a[i]+=a[i-1];
//printf("%d",a[i]);
if(a[i]>r[i])
return false;
}
return true;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&r[i]);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&d[i],&s[i],&t[i]);
int l=0,r=m;
while(l<r)
{
int mid=l+r+1>>1;
if(cheke(mid,n))
l=mid;
else
r=mid-1;
}
if(r == m)
printf("0");
else
printf("-1\n%d\n",l+1);
}