/* 维护区间最小值 数据不超int 相反如果long long的话会有一组数据超时 无视掉 ll int */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 1000010 #define ll int #define inf 0x7fffffff using namespace std; ll n,m,num,a[maxn],falg; struct node { ll lc,rc,l,r,bj,ans; }t[maxn*2]; ll init() { ll x=0;char s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } void Build(ll li,ll ri) { ll k=++num; t[k].l=li;t[k].r=ri; if(li!=ri-1) { t[k].lc=num+1; Build(li,(li+ri)/2); t[k].rc=num+1; Build((li+ri)/2,ri); t[k].ans=min(t[t[k].lc].ans,t[t[k].rc].ans); } else t[k].ans=a[li]; } void update(ll k) { t[t[k].lc].ans-=t[k].bj; t[t[k].rc].ans-=t[k].bj; t[t[k].lc].bj+=t[k].bj; t[t[k].rc].bj+=t[k].bj; t[k].bj=0; } void change(ll k,ll li,ll ri,ll p) { if(falg)return; if(li<=t[k].l&&ri>=t[k].r) { t[k].ans-=p; if(t[k].ans<0)falg=1; t[k].bj+=p; return; } if(t[k].bj)update(k); if(li<(t[k].l+t[k].r)/2)change(t[k].lc,li,ri,p); if(ri>(t[k].l+t[k].r)/2)change(t[k].rc,li,ri,p); t[k].ans=min(t[t[k].lc].ans,t[t[k].rc].ans); } int main() { n=init();m=init(); for(int i=1;i<=n;i++) a[i]=init(); Build(1,1+n); int x,y,z; for(int i=1;i<=m;i++) { falg=0; x=init();y=init();z=init(); change(1,y,z+1,x); if(falg==1) { printf("-1 %d ",i); return 0; } } printf("0 "); return 0; }
/* 后来听说二分快 果然快好多 - - 首先如果我们不会线段树的话 朴素的做法是对于每个询问 O(n)修改 O(n)查询 慢的很 差分这个东西可以实现O(2)的修改 O(n)还原 O(n)查询 优化一下的话 边还原边查询 这样就好多了 然后二分查询到哪一个任务 （反正考试的话我是想不到0.0） */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 1000010 using namespace std; int n,m,ans,a[maxn],s[maxn]; struct node { int li,ri,ti; }p[maxn]; bool can(int x) { memset(s,0,sizeof(s)); int sum=0; for(int i=1;i<=x;i++) { s[p[i].li]+=p[i].ti; s[p[i].ri+1]-=p[i].ti; } for(int i=1;i<=n;i++) { sum+=s[i]; if(sum>a[i])return 0; } return 1; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) scanf("%d%d%d",&p[i].ti,&p[i].li,&p[i].ri); int l=0,r=m; while(l<=r) { int mid=(l+r)/2; if(can(mid)==0) { ans=mid; l=mid+1; } else r=mid-1; } if(!ans)printf("0 "); else printf("-1 %d",ans); return 0; }