#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010;
int n, m;
int w[N];
int l[N], r[N], d[N];
LL b[N];
bool check(int mid)
{
memset(b, 0, sizeof b);
for (int i = 1; i <= mid; i ++ )
{
b[l[i]] += d[i];
b[r[i] + 1] -= d[i];
}
for (int i = 1; i <= n; i ++ )
{
b[i] += b[i - 1];
if (b[i] > w[i]) return false;
}
return true;
}
int main()
{ //用到差分 且题目记录都是从1开始,最好直接从1开始
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
scanf("%d", &w[i]);
for (int i = 1; i <= m; i ++ )
scanf("%d%d%d", &d[i], &l[i], &r[i]);
//l从1开始时需要特判 具体原因看下边链接
//总之做题时注意边界条件,直接让l=0就不用考虑边界条件了
int l = 0, r = m;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
if (r == m) puts("0");
else printf("-1\n%d\n", r + 1);
return 0;
}
l从0开始,举例理解
或 看评论区