[NOIP2012]借教室

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int n, m, a[N];
struct node {
  int l;
  int r;
  int lz;
  int w;
} tr[N << 2];
void pushdown(int u) {
  if (tr[u].lz) {
    tr[u << 1].w -= tr[u].lz;
    tr[u << 1 | 1].w -= tr[u].lz;
    tr[u << 1].lz += tr[u].lz;
    tr[u << 1 | 1].lz += tr[u].lz;
    tr[u].lz = 0;
  }
}
void pushup(int u) {
  tr[u].w = min(tr[u << 1].w, tr[u << 1 | 1].w);
}
void build(int u, int l, int r) {
  tr[u] = {l, r, 0};
  if (l == r) {
    tr[u].w = a[l];
    return;
  }
  int mid = l + r >> 1;
  build(u << 1, l, mid);
  build(u << 1 | 1, mid + 1, r);
  pushup(u);
}
void  update(int u, int l, int r, int k) {
  if (tr[u].l >= l && tr[u].r <= r) {
    tr[u].w -= k;
    tr[u].lz += k;
    return ;
  }
  pushdown(u);
  int mid = tr[u].l + tr[u].r >> 1;
  if (l <= mid) update(u << 1, l, r, k);
  if (r > mid)  update(u << 1 | 1, l, r, k);
  pushup(u);
  return ;
}
bool query(int u, int l, int r) {
  if (tr[u].l >= l && tr[u].r <= r) {
    if (tr[u].w <0) return false;
    else return true;
  }
  pushdown(u);
  int mid = tr[u].l + tr[u].r >> 1;
  bool f1 = 1, f2 = 1;
  if (l <= mid) f1 = query(u << 1, l, r);
  if (r > mid) f2 = query(u << 1 | 1, l, r);
  return f1 &f2;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  build(1, 1, n);
  int d, s, t;
  bool f = 1;
  int cnt = 1;
  for (int T = 1; T <= m; T++) {
    scanf("%d%d%d", &d, &s, &t);
    bool ok = true;
        update(1, s, t, d);
    ok = query(1, s, t);
    if (!ok) {
      f = 0;
      cout << -1 << "\n";
      cout << T << "\n";
      break;
    }
  }
  if (f) cout << 0 << "\n";
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,c[N],d[N],t[N],s[N],r[N];
inline bool check(int x)
{
    memset(c,0,sizeof c);
    for(int i=1;i<=x;i++)
    {
        c[s[i]]+=d[i];
        c[t[i]+1]-=d[i];
    }
    for(int i=1;i<=n;i++)
    {
        c[i]+=c[i-1];
        if(c[i]>r[i]) return true;
    }
    return false;
}
int main()
{
    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]);
    if(!check(m))
    {
        cout<<0<<"\n";
        return 0;
    }
    int l=0,r=m;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;//chushi
        else l=mid+1;
    }
    printf("-1\n%d\n",l);
}