题解 P1083 【借教室】

2018-07-06 18:29:31


由于只用输出第一个不满足条件的编号,所以可以二分这个人的编号。

对于每一个二分出来的编号,进行检验,看在这个人之前的操作是否符合要求

处理区间操作时,可以用差分进行维护

#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;
}