经典题
二分 + 前缀和
注意long long 和初始化change[] //QAQ
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 #define ll long long //注意long long
6
7 using namespace std;
8 const int N = 1000000 + 5;
9 ll n,m;
10 ll d[N],sum[N],c[N],a[N],b[N],change[N];
11 bool bo;
12 bool check(ll x){
13 memset(change,0,sizeof(change)); //注意初始化QAQ
14 for(int i = 1;i <= x;++ i){
15 change[a[i]] += c[i];
16 change[b[i] + 1] -= c[i];
17 }
18 ll sum = 0;
19 for(int i = 1;i <= n;++ i){
20 sum += change[i];
21 if(sum > d[i]) return true;
22 }
23 return false;
24 }
25 int main(){
26 scanf("%lld%lld",&n,&m);
27 for(int i = 1;i <= n;++ i){
28 scanf("%lld",&d[i]);
29 }
30 for(int i = 1;i <= m;++ i){
31 scanf("%lld%lld%lld",&c[i],&a[i],&b[i]);
32 }
33 ll l = 0,r = m; // l :不可能，r:可能
34 while(r - l > 1){
35 ll mid = (l + r) >> 1;
36 if(check(mid)){
37 r = mid;
38 bo = 1; //有输出的可能值
39 }
40 else{
41 l = mid;
42 }
43 }
44 if(bo){
45 cout << "-1" << '
';
46 cout << r << '
'; //输出可能值r
47 }
48 else{
49 cout << "0" << '
';
50 }
51 return 0;
52 }