据说这题原来考察的就是二分优化。。。布吉怎的就变成线段树模版了、、、

#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 1000001
#define CLR(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m;
int d[maxn],s[maxn],t[maxn],r[maxn],delta[maxn];
void operate(int x){
delta[s[x]]+=d[x];
delta[t[x]+1]-=d[x];
return;
}
bool possible(int x){
CLR(delta,0);
int temp=0;
for (int i=1;i<=x;i++) operate(i);
for (int i=1;i<=n;i++){
temp+=delta[i];
if (temp>r[i]) return false;
}
return true;
}
void binary(int l,int r){
if (l==r) {
printf("-1\n");
printf("%d\n",l);
exit(0);
} else {
int mid=(l+r)/2;
if (possible(mid)) binary(mid+1,r); else binary(l,mid);
}
return;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&r[i]);
for (int i=1;i<=m;i++)
scanf("%d%d%d",&d[i],&s[i],&t[i]);
if (possible(m)) {
printf("0\n");
return 0;
}
//for (int i=1;i<=m;i++) printf("%d ",possible(i)?1:0);
binary(1,m);
return 0;
}

Orz

Orz
原来写线段树一直tle
后来改成2s过了
然后写二分 又tle了
二分t的线段树可过
于是丧心病狂的结合在一起了。。。
还写了个readint()...