可以线段树或者二分。
线段树会被卡，二分写不好也会被卡。
所以用二分。
读入用getchar()的话可以减少一半以上的时间。
#include <cstdio>
const int N = 1000000 + 9;
long long delta[N];
int idx[N],a[N],n,m,d[N],s[N],t[N],pre;
inline bool check(const int mid)
{
long long sum = 0;
if (pre < mid)
for (int i = pre + 1; i <= mid; ++i)
delta[s[i]] += d[i],delta[t[i] + 1] -= d[i];
else
for (int i = mid + 1; i <= pre; ++i)
delta[s[i]] -= d[i],delta[t[i] + 1] += d[i];
pre = mid;
for (int i = 1; i <= n; ++i)
if ((sum += delta[i]) > a[i]) return false;
return true;
}
inline void read(int &x)
{
char c;
while ((c = getchar()) < '0');
while (c >= '0') {
x = x * 10 + c - '0';
c = getchar();
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("classroom.in","r",stdin);
freopen("classroom.out","w",stdout);
#endif
read(n);read(m);
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = 1; i <= m; ++i) {
read(d[i]);read(s[i]);read(t[i]);
}
int l = 0,r = n + 1;
while (l + 1 < r) {
const int mid = (l + r)/2;
if (check(mid)) l = mid;
else r = mid;
}
if (l == n) puts("0");
else printf("-1
%d
",r);
}