题目:
const int N = 1e6 + 10;
int a[N], d[N], t[N], s[N], ch[N];
int n, m;
bool sb(int x)
{
memset(ch, 0, sizeof ch);
//起初都是默认为0的数组,然后再进行差分
for(int i = 1; i <= x; i ++)
{
ch[s[i]] += d[i];
ch[t[i] + 1] -= d[i];
}
for(int i = 1; i <= n; i ++)
{
ch[i] += ch[i - 1];//前缀和
if(ch[i] > a[i]) return 0;
}
return 1;
}
void solved()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= m; i ++)
cin >> d[i] >> s[i] >> t[i];
if(sb(m))
{
cout << "0" << endl;
return;
}
int l = 1, r = m;
while(l < r)//二分
{
int mid = (l + r) >> 1;
if(!sb(mid)) r = mid;
else l = mid + 1;
}
cout << "-1" << endl << l << endl;
}