题解 P1083 【借教室】
hicc0305
2018-07-06 18:29:31
由于只用输出第一个不满足条件的编号，所以可以二分这个人的编号。
对于每一个二分出来的编号，进行检验，看在这个人之前的操作是否符合要求
处理区间操作时，可以用差分进行维护
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int a[1000100],c[1000100],tmp[1000100];
int d[1000100],s[1000100],t[1000100];
bool check(int k)
{
memcpy(c,tmp,sizeof(c));
for(int i=1;i<=k;i++)
c[s[i]]-=d[i],c[t[i]+1]+=d[i];
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]+c[i];
if(a[i]<0) return 0;
}
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),c[i]=a[i]-a[i-1];
memcpy(tmp,c,sizeof(tmp));
for(int i=1;i<=m;i++)
scanf("%d%d%d",&d[i],&s[i],&t[i]);
if(check(m))
{
cout<<0;
return 0;
}
int l=1,r=m;
while(l<r)
{
int mid=(l+r)/2;
if(check(mid)) l=mid+1;
else r=mid;
}
cout<<-1<<endl<<l;
return 0;
}
```