noip2012借教室

答案满足单调性 二分即可

以前缀和的形式存储每天需要教室的数量 计算时暴力O（n）算出每天教室的数量

这样总复杂度nlogn

ps:自己真是作死居然用cin..AC代码被cin卡到45

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#define N 1000001
using namespace std;
int r[N];
int m,n,x[N],y[N],s[N];
long long f[N];
int main()
{
    
    cin>>n>>m;
    for (int i=1;i<=n;i++)
      scanf("%d",&r[i]);
    for (int i=1;i<=m;i++)
    {
      scanf("%d%d%d",&s[i],&x[i],&y[i]);
    }
    int zuo,you;
    zuo=1;
    you=m+1;
    while (zuo!=you)
    {
      int mid=(zuo+you)/2;
      int ss=0;
      for (int i=zuo;i<=mid;i++)
      {
        f[x[i]]+=s[i];
        f[y[i]+1]-=s[i];
      }
      int ff=0;
      for (int i=1;i<=n;i++)
      {
        ss+=f[i];
        if (ss>r[i])
        {
          ff=1;
          break;
        }
      }
      if (ff==1)
      {
        for (int i=zuo;i<=mid;i++)
        {
          f[x[i]]-=s[i];
          f[y[i]+1]+=s[i];
        }
        you=mid;
      }
      else
        zuo=mid+1;
    }
    if (zuo==m+1)
    {
      printf("0");

      return 0;
    }
    else
    {
      printf("-1
");
      printf("%d",zuo);
   
    }
}