差分数组维护前缀和，之后从后往前判断是否合法，找到尽量位置在后的合法位置，判断输出就好了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<stack> 7 #include<deque> 8 #include<algorithm> 9 #define ll long long 10 using namespace std; 11 const ll oo=0x3f3f3f3f; 12 const ll N=1000005; 13 14 ll n,m,x=-1,sum; 15 ll a[N],c[N],l[N],r[N],cf[N]; 16 bool flag=1; 17 18 ll Min(ll a,ll b){return a<b?a:b;} 19 ll Max(ll a,ll b){return a>b?a:b;} 20 ll Abs(ll a){return a>0?a:-a;} 21 22 ll get(){ 23 char zy=getchar(); 24 ll z=1,y=0; 25 while(zy>'9'||zy<'0'){ 26 if(zy=='-') z=-1; 27 zy=getchar(); 28 } 29 while(zy>='0'&&zy<='9'){ 30 y=(y<<1)+(y<<3)+zy-'0'; 31 zy=getchar(); 32 } 33 return z*y; 34 } 35 36 int main(){ 37 n=get();m=get(); 38 for(ll i=1;i<=n;i++) a[i]=get(); 39 for(ll i=1;i<=m;i++){ 40 c[i]=get();l[i]=get();r[i]=get(); 41 cf[l[i]]+=c[i]; 42 cf[r[i]+1]-=c[i]; 43 } 44 ll j=m; 45 for(ll i=1;i<=n;i++){ 46 sum+=cf[i]; 47 if(sum>a[i]){ 48 while(sum>a[i]){ 49 cf[l[j]]-=c[j]; 50 cf[r[j]+1]+=c[j]; 51 if(l[j]<=i&&i<=r[j]) sum-=c[j]; 52 j--; 53 } 54 if(flag){ 55 x=j; 56 flag=0; 57 } 58 else x=min(x,j); 59 } 60 } 61 if(x==-1)printf("0 "); 62 else printf("-1 %lld ",x+1); 63 return 0; 64 }