————————————————————————————————————--
今日份的1A+独立思考+短时间
本来准备写线段树的,刚开始写就想到了
这tm直接差分不就行了
一开始还以为会T几个点,结果直接A了
好水的DAY2
不过刚学了树上差分,如果没学可能现在还在调线段树吧
QAQ
#include<bits/stdc++.h> using namespace std; int num[1010000],dd[1010000],op[1010000],ed[1010000],n,m,cf[1010000]; inline int read() { int ans=0; char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9') {ans=ans*10+ch-'0';ch=getchar();} return ans; } inline int check(int t) { memset(cf,0,sizeof(cf)); for(int i=1;i<=t;i++) {cf[op[i]]-=dd[i];cf[ed[i]+1]+=dd[i];} for(int i=1;i<=n;i++) {cf[i]+=cf[i-1];if(cf[i]+num[i]<0)return 0;} return 1; } int main() { cin>>n>>m; for(int i=1;i<=n;i++)num[i]=read(); for(int i=1;i<=m;i++){dd[i]=read();op[i]=read();ed[i]=read();} if(check(m)){cout<<0;return 0;} int l=1,r=m-1,ans=0; while(l<=r) { int mid=(l+r)>>1; if(check(mid))ans=mid,l=mid+1; else r=mid-1; } cout<<-1<<endl<<ans+1; }