记录编号	445736	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	_WA自动机	是否通过	通过
代码语言	C++	运行时间	1.946 s
提交时间	2017-09-06 17:57:32	内存使用	23.18 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<climits>
#include<cctype>
using namespace std;
const int maxn=1e6+10;
int n,r[maxn],m,d[maxn],s[maxn],t[maxn];long long delta[maxn];
inline bool check(int i)
{
    memset(delta,0,sizeof(delta));
    for (int j=1;j<=i;++j)
    {
        delta[s[j]]-=d[j];
        delta[t[j]+1]+=d[j];
    }
    long long sum=0;
    for (int j=1;j<=n;++j)
    {
        sum+=delta[j];
        if (sum+r[j]<0) return false;
    }
    return true;
}
int main()
{
    #ifndef COGS
    freopen("classrooms.in","r",stdin);
    freopen("classrooms.out","w",stdout);
    #endif // COGS
    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+1,mid,ans;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if (check(mid)) {l=mid+1;ans=mid;}
        else r=mid-1;
    }
    if (r==m+1) putchar(48);else printf("-1\n%d\n",ans+1);
    return 0;
}