基于差分、单调性的二分法
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
int n,m;
int r[N],d[N],s[N],t[N];
LL b[N];//差分数组
bool check(int mid)
{
//差分数组
for(int i=1;i<=n;i++) b[i]=r[i]-r[i-1];
//前mid家
for(int i=1;i<=mid;i++)
{
int l=s[i],r=t[i],w=d[i];
b[l]-=w,b[r+1]+=w;
}
//对b求前缀和
for(int i=1;i<=n;i++)
{
b[i]+=b[i-1];
if(b[i]<0) return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>r[i];
for(int i=1;i<=m;i++) cin>>d[i]>>s[i]>>t[i];
int l=0,r=m;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
if(r==m) cout<<0<<endl;
else cout<<-1<<endl<<r+1<<endl;
return 0;
}