[数据结构与算法]P1083借教室（前缀和+差分+二分答案）

P1083 [NOIP2012 提高组] 借教室https://www.luogu.com.cn/problem/P1083

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int a[N],dif[N],temp[N];
int d[N],s[N],t[N];
int n,m;
bool check(int x)
{
	memset(dif,0,sizeof(dif));
	for(int i=1;i<=x;i++)
	{
		dif[s[i]]-=d[i];
		dif[t[i]+1]+=d[i];
	}
	for(int i=1;i<=n;i++)
	{
		temp[i]=temp[i-1]+dif[i];
		if(temp[i]+a[i]<0) return 0;
	}
	return 1;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int j=1;j<=m;j++)
		scanf("%d%d%d",&d[j],&s[j],&t[j]);
	if(check(m))
	{
		cout<<'0';
		return 0;
	}
	int l=1,r=m,mid,ans;
	while(l<r)
	{
		mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else r=mid;
	}
	cout<<"-1\n"<<l;
}