在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 n 天的借教室信息，其中第 i 天学校有 ri​ 个教室可供租借。共有 m 份订单，每份订单用三个正整数描述，分别为 dj​,sj​,tj​，表示某租借者需要从第 sj​ 天到第 tj​ 天租借教室（包括第 sj​ 天和第 tj​ 天），每天需要租借 dj​ 个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 dj​ 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 sj​ 天到第 tj​ 天中有至少一天剩余的教室数量不足 dj​ 个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 n,m，表示天数和订单的数量。

第二行包含 n 个正整数，其中第 i 个数为 ri​，表示第 i 天可用于租借的教室数量。

接下来有 m 行，每行包含三个正整数 dj​,sj​,tj​，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 1 开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数 0。否则（订单无法完全满足）

输出两行，第一行输出一个负整数 −1，第二行输出需要修改订单的申请人编号。

输入输出样例

输入 #1复制

4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4

输出 #1复制

-1 
2

//读题不难发现每一个订单会对一个区间的值同时操作 我们可以用一个差分数组来维护这个区间  将这个区间的值同时减去每个订单所需要的教室数量  同时我们可以注意到 当订单的数量增多时教室的数量就越少 教室数量越少就越不容易满足之后的订单  题目说按照订单顺序来借教室 可以通过二分来找到最后一个满足条件的订单  就是二分订单找到最大能满足多少个订单  最大满足订单的下一个订单就是需要修改订单的编号 如果能满足所有订单就输出0

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+10;
int n,m;
int x,st,ed;
int a[N],b[N];
struct Node{
    int d,st,ed;
}node[N];//记录订单需要的教室数量 起始的天数 和结束的天数

bool check(int x){
    for(int i = 1;i <= n;i ++) a[i] = b[i]; //复制一份差分数组
    for(int i = 1;i <= x;i ++) {
        int u = node[i].st,v = node[i].ed;
        a[u] -= node[i].d;//将[l,n]的区间全部减去d,  [r+1,n]区间加上d
        a[v + 1] += node[i].d;
    }
    for(int i = 1;i <= n;i ++) {
        a[i] += a[i - 1];//求一遍前缀和计算出当前所有教室的剩余数量
        if(a[i] < 0) return false;//如果有一个小于0 就不能满足给这个订单
    }
    return true;
}


int main() {
    scanf("%d%d",&n,&m);
    for(int i =1 ;i<=n;i++){
        scanf("%d",&a[i]);
        b[i] = a[i] - a[i-1];
    }//维护一个差分数组b
    for(int i = 1;i<=m;i++){
        scanf("%d%d%d",&x,&st,&ed);
        node[i]={x,st,ed};
    }//输入订单顺序
    //二分查找
    int l = 0,r = m+1;
    while(l+1<r){ 
        int mid = l+r>>1;
        if(check(mid))l=mid; //订单数量少了  还可以满足更多订单
        else r = mid;
    }
    //如果能满足所有的订单就不用修改订单的信息
    if(l == m)cout<<0<<endl;
    else cout<<-1<<endl<<l+1;
}