- 借教室
- 2013-09-25 19:18:21 @
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int MAX=1000000+10;
int N,M,a[MAX],i,d[MAX],L[MAX],R[MAX],g[MAX];
template <class T> T get(T &u){
char x;for(;!isdigit(x=getchar()););
for(u=x-48;isdigit(x=getchar());u*=10,u+=(x-48));
ungetc(x,stdin);return u;
}
int check(int mid){
int i;
memset(g,0,(N+2)*sizeof(int));
for(i=1;i<=mid;++i){
g[L[i]]+=d[i];
g[R[i]+1]-=d[i];
}
int now=0;
for(i=1;i<=N;++i){
now+=g[i];
if(now>a[i])return 0;
}
return 1;
}
int main(){
get(N);get(M);
for(i=1;i<=N;++i) get(a[i]);
for(i=1;i<=M;++i) get(d[i]),get(L[i]),get(R[i]);
int l=0,r=M,m;
while(l<r){
m=(l+r)>>1;
if(check(m))l=m+1;
else r=m;
}
if(r==M) puts("0");
else puts("-1"),printf("%d",l);
return 0;
}
2 条评论
-
yyh5900 LV 8 @ 2015-05-29 22:39:00
不要吧= =
-
2013-11-03 15:05:11@
信息学是你的最佳选择!~
- 1