#include <iostream>
#include <stdio.h>

using namespace std;

int value[4 * 1000000];
int tag[4 * 1000000];
int a[1000000 + 2];

inline int min( int a , int b )
{
if( a > b )
return b;
return a;
}

inline void pushdown( int n , int l , int r )
{
if( l == r )
value[n] += tag[n];
else
{
tag[ n << 1 ] += tag[n];
tag[ ( n << 1 ) + 1 ] += tag[n];
value[n] = min( value[ n << 1 ] + tag[ n << 1 ] , value[ ( n << 1 ) + 1 ] + tag[ ( n << 1 ) + 1 ] );
}
tag[n] = 0;
return;
}

int build( int n , int l , int r )
{
if( l == r )
return value[n] = a[l];
return value[n] = min( build( n << 1 , l , ( l + r ) >> 1 ) , build( ( n << 1 ) + 1 , ( ( l + r ) >> 1 ) + 1 , r ) );
}

int find( int n , int l , int r , int a , int b , int v )
{
pushdown( n , l , r );
if( l == a && r == b )
{
tag[n] -= v;
pushdown( n , l , r );
return value[n];
}
int mid = ( l + r ) >> 1;
if( a > mid )
{
int ans = find( ( n << 1 ) + 1 , mid + 1 , r , a , b , v );
pushdown( n , l , r );
return ans;
}
else if( mid >= b )
{
int ans = find( n << 1 , l , mid , a , b , v );
pushdown( n , l , r );
return ans;
}
int ans = min( find( n << 1 , l , mid , a , mid , v ) , find( ( n << 1 ) + 1 , mid + 1 , r , mid + 1 , b , v ) );
pushdown( n , l , r );
return ans;
}

int n , m;
int l , r , v;
int i;

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 1 ; i <= n ; i++ )
scanf( "%d" , &a[i] );
build( 1 , 1 , n );
for( i = 1 ; i <= m ; i++ )
{
scanf( "%d %d %d" , &v , &l , &r );
if( find( 1 , 1 , n , l , r , v ) < 0 )
{
printf( "-1\n%d\n" , i );
return 0;
}
}
printf( "0\n" );
return 0;
}
95分。。。。。。

这题暴力加和都可以得40分，但要都过得二分订单+前缀和+优化判定单才能AC
#include<iostream>
#include<cstdio>
#include<cstring>
int n,m,l=1,r;
int a[1000005],d[1000005];
int s[1000005];
int e[1000005];
long long q[1000005],p[1000005];
using namespace std;

int judge(int x,int temp)
{
int i,sum=0,b=0;
if(temp==0) for(i=1;i<=x;i++) {q[s[i]]=q[s[i]]+d[i]; q[e[i]+1]=q[e[i]+1]-d[i];} //第一次加载，前缀和
if(temp==1) for(i=l;i<=x;i++) {q[s[i]]=q[s[i]]+d[i]; q[e[i]+1]=q[e[i]+1]-d[i];}

if(temp==2) for(i=x+1;i<=r+1;i++) {q[s[i]]=q[s[i]]-d[i]; q[e[i]+1]=q[e[i]+1]+d[i];} //防止重复加载
for(i=1;i<=n;i++) {sum+=q[i]; p[i]=sum;}
for(i=1;i<=n;i++) if(p[i]>a[i]) b=1; //线段树处理
if(b==1) return 0;
return 1;
}

int main()
{

int i,mid,ans=-1,z=0;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=1;i<=m;i++) scanf("%d %d %d",&d[i],&s[i],&e[i]);
r=m;
while(l<=r)
{
mid=(l+r)/2;
if(judge(mid,z)) {ans=mid; l=mid+1; z=1;}
else {r=mid-1; z=2;}
} //二分订单
if(ans==m) printf("0"); //全都行
else {
if(ans==-1) ans=0; //全不行
printf("-1\n%d",ans+1); //中间开始不行
}
return 0;
}

懒标记线段树+读入优化 最高1600ms险过

#include<stdio.h>
struct segtree
{
int left,right,cover,mark;
};

struct segtree tree[6000010];

int n,m,bools[1000000]={0},flag=0,minnum=1000000000;

inline int read( )
{
int x=0;
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
x=0;
while (ch<='9' && ch>='0')
{
x*=10,x+=ch-'0';
ch=getchar();
}
return x;
}

int min(int a,int b)
{
if(a<b) return a;
else return b;
}

void build(int p,int a,int b)
{
tree[p].left=a;
tree[p].right=b;
tree[p].mark=0;

if(b-a>1)
{
build(p*2,a,(a+b)/2);
build(p*2+1,(a+b)/2,b);
tree[p].cover=min(tree[p*2].cover,tree[p*2+1].cover);
}

else tree[p].cover=bools[a];
}

void pushmark(int p)
{
tree[p*2].mark=tree[p*2].mark+tree[p].mark;
tree[p*2+1].mark=tree[p*2+1].mark+tree[p].mark;
tree[p*2].cover=tree[p*2].cover+tree[p].mark;
tree[p*2+1].cover=tree[p*2+1].cover+tree[p].mark;
tree[p].mark=0;
}

void insert(int p,int a,int b,int value)
{

if(a==tree[p].left && b==tree[p].right)

{
tree[p].cover=tree[p].cover+value;
tree[p].mark=tree[p].mark+value;
}

else
{
int mid;
mid=(tree[p].left+tree[p].right)/2;

if(a>=mid)
{
pushmark(p);
insert(p*2+1,a,b,value);
tree[p].cover=min(tree[p].cover,tree[p*2+1].cover);
}

else if(b<=mid)
{
pushmark(p);
insert(p*2,a,b,value);
tree[p].cover=min(tree[p].cover,tree[p*2].cover);
}

else
{
pushmark(p);
insert(p*2,a,mid,value);
insert(p*2+1,mid,b,value);
tree[p].cover=min(tree[p].cover,tree[p*2+1].cover);
tree[p].cover=min(tree[p].cover,tree[p*2].cover);
}

}
}

void getmin(int p,int a,int b)
{

if(a==tree[p].left && b==tree[p].right)

minnum=min(minnum,tree[p].cover);

else
{
pushmark(p);
int mid;
mid=(tree[p].left+tree[p].right)/2;

if(a>=mid)
getmin(p*2+1,a,b);

else if(b<=mid)
getmin(p*2,a,b);

else
{
getmin(p*2,a,mid);
getmin(p*2+1,mid,b);
}

}
}

int main( )
{

int i,x1,x2,x3;

n=read( );
m=read( );

for(i=1;i<=n;i++)
bools[i]=read( );

build(1,1,n+1);

for(i=1;i<=m;i++)
{
x1=read( );
x2=read( );
x3=read( );
insert(1,x2,x3+1,-x1);
getmin(1,x2,x3+1);
if(minnum<0) {printf("-1\n");printf("%d",i);flag=1;break;}

}

if(flag==0) printf("0");

return 0;
}

评测机真坑！在本地1s不开优化AC，在这2s开O2TLE，醉了，醉了。。。
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int tree[4000001],tag[4000001],num,day[1000001],tmp;

inline int min(int a,int b) {
return a<b?a:b;
}

inline void update(int pos) {
if(tag[pos]==0) return;
tag[pos<<1]+=tag[pos];
tag[(pos<<1)+1]+=tag[pos];
tree[(pos<<1)+1]+=tag[pos];
tree[pos<<1]+=tag[pos];
tag[pos]=0;
}

void insert(int pos,int l,int r,int ll,int rr,int delta) {
if(ll<=l&&r<=rr) {
tree[pos]+=delta;
if(tree[pos]<0){
printf("-1\n%d",num);
exit(0);
}
tag[pos]+=delta;
return;
}
update(pos);
int mid=(l+r)>>1;
if(ll<mid) insert(pos<<1,l,mid,ll,rr,delta);
if(mid<rr) insert((pos<<1)+1,mid,r,ll,rr,delta);
tree[pos]=min(tree[pos<<1],tree[(pos<<1)+1]);
}

void read(int &x) {
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
x=0;
while(ch<='9'&&ch>='0'){
x=x*10+ch-'0';
ch=getchar();
}
}

void build(int pos,int l,int r) {
if(l+1==r){
read(tmp);
tree[pos]=tmp;
return;
}
int mid=(l+r)>>1;
build(pos<<1,l,mid);
build((pos<<1)+1,mid,r);
tree[pos]=min(tree[(pos<<1)+1],tree[pos<<1]);
}

int main() {
int N,M,tmp;
read(N);
read(M);
build(1,1,N+1);
for(int i=1,d,s,t;i<=M;i++)
{
read(d);
read(s);
read(t);
num=i;
insert(1,1,N+1,s,t+1,-d);
}
putchar('0');
return 0;
}

线段树+读入优化。。。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int Min[4000006],Tag[4000006],M,n,m;
const int INF=~0U>>2;
void Down(int pos)
{
for (int k=M;k;k>>=1)
{
int s=pos/k;
if (0==Tag[s] || s+s>M+M+M) continue;
Tag[s<<1]+=Tag[s],Min[s<<1]+=Tag[s];
Tag[(s<<1)^1]+=Tag[s],Min[(s<<1)^1]+=Tag[s];
Tag[s]=0;
}
}
void Up(int pos)
{
for (int i=pos>>1;i;i>>=1) Min[i]=min(Min[i<<1],Min[(i<<1)+1])+Tag[i];
}
int Get_Min(int l,int r)
{
int ans=INF;
l=l+M-1,r=r+M+1;
Down(l),Down(r);
for (int s=l,t=r;s^1^t;s>>=1,t>>=1)
{
if (~s&1) ans=min(ans,Min[s^1]);
if (t&1) ans=min(ans,Min[t^1]);
}
return ans;
}
void Add(int l,int r,int k)
{
l=l+M-1,r=r+M+1;
Down(l),Down(r);
for (int s=l,t=r;s^1^t;s>>=1,t>>=1)
{
if (~s&1) Tag[s^1]+=k,Min[s^1]+=k;
if (t&1) Tag[t^1]+=k,Min[t^1]+=k;
}
Up(l),Up(r);
}
inline void Read(int &x)
{
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
x=0;
while (ch<='9' && ch>='0')
{
x*=10,x+=ch-'0';
ch=getchar();
}
}
int main()
{
scanf("%d%d",&n,&m);
for (M=1;M<=n+1;M<<=1);
for (int i=1;i<=n;i++) Read(Min[M+i]);//scanf("%d",Min+M+i);
for (int i=M-1;i;i--) Min[i]=min(Min[(i<<1)+1],Min[i<<1]);
for (int i=1,d,s,t;i<=m;i++)
{
Read(d),Read(s),Read(t);//scanf("%d%d%d",&d,&s,&t);
int x=Get_Min(s,t);
if (x<d)
{
puts("-1");
printf("%d\n",i);
return 0;
}
Add(s,t,-d);
}
puts("0");
return 0;
}

#include<cstdio>
#include<cstring>
#define N 1000010
using namespace std;
struct lr{int l,r,num;}a[N];
int lim[N],n,m,f[N];
bool check(int x)
{
memset(f,0,sizeof(f));
int ret=0,i;
for(i=1;i<=x;++i)
{
f[a[i].l]+=a[i].num;
f[a[i].r+1]-=a[i].num;
}
for(i=1;i<=n;++i)
{
ret+=f[i];
if (ret>lim[i]) return 0;
}
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
int i,l,r,mid;
for(i=1;i<=n;++i) scanf("%d",&lim[i]);
for(i=1;i<=m;++i)
scanf("%d%d%d",&a[i].num,&a[i].l,&a[i].r);
l=1; r=m+1;
while (l<r)
{
mid=l+r>>1;
if (check(mid)) l=mid+1;
else r=mid;
}
if (l>m) puts("0");
else printf("-1\n%d",l);
return 0;
}

给二分加了个奇怪的小剪枝就卡着时限过了

这道题的测试数据不科学啊

为什么我打的NOIP2012的AC程序到这儿就变95了？

var
n,m,i,l,r,now,k,ssum:longint;
room,d,s,t,sum:array[0..1000001]of longint;
flag:boolean;
procedure init;
begin
read(n,m);
for i:=1 to n do
read(room[i]);
for i:=1 to m do
read(d[i],s[i],t[i]);
end;
procedure print;
begin
write(0);
halt;
end;
procedure work;
begin
now:=0;
l:=0;
r:=m+1;
repeat
flag:=true;
k:=(l+r)shr 1;
if k>now then
for i:=now+1 to k do
begin
inc(sum[s[i]],d[i]);
dec(sum[t[i]+1],d[i]);
end
else
for i:=k+1 to now do
begin
dec(sum[s[i]],d[i]);
inc(sum[t[i]+1],d[i]);
end;
now:=k;
ssum:=0;
for i:=1 to n do
begin
inc(ssum,sum[i]);
if ssum>room[i] then begin flag:=false; break; end;
end;
if flag then l:=k+1
else r:=k;
until l=r;
if (k=m)and(flag) then print;
writeln(-1);
write(l);
end;
begin
init;
work;
end.

二分查找
VijosEx via JudgeDaemon2/13.4.6.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 19 ms, mem = 32036 KiB, score = 5
测试数据 #1: Accepted, time = 3 ms, mem = 32040 KiB, score = 5
测试数据 #2: Accepted, time = 5 ms, mem = 32040 KiB, score = 5
测试数据 #3: Accepted, time = 2 ms, mem = 32040 KiB, score = 5
测试数据 #4: Accepted, time = 7 ms, mem = 32044 KiB, score = 5
测试数据 #5: Accepted, time = 5 ms, mem = 32040 KiB, score = 5
测试数据 #6: Accepted, time = 35 ms, mem = 32036 KiB, score = 5
测试数据 #7: Accepted, time = 31 ms, mem = 32040 KiB, score = 5
测试数据 #8: Accepted, time = 31 ms, mem = 32044 KiB, score = 5
测试数据 #9: Accepted, time = 35 ms, mem = 32044 KiB, score = 5
测试数据 #10: Accepted, time = 31 ms, mem = 32040 KiB, score = 5
测试数据 #11: Accepted, time = 27 ms, mem = 32040 KiB, score = 5
测试数据 #12: Accepted, time = 31 ms, mem = 32040 KiB, score = 5
测试数据 #13: Accepted, time = 31 ms, mem = 32040 KiB, score = 5
测试数据 #14: Accepted, time = 309 ms, mem = 32036 KiB, score = 5
测试数据 #15: Accepted, time = 317 ms, mem = 32040 KiB, score = 5
测试数据 #16: Accepted, time = 313 ms, mem = 32040 KiB, score = 5
测试数据 #17: Accepted, time = 313 ms, mem = 32040 KiB, score = 5
测试数据 #18: Accepted, time = 317 ms, mem = 32040 KiB, score = 5
测试数据 #19: Accepted, time = 309 ms, mem = 32040 KiB, score = 5
Accepted, time = 2181 ms, mem = 32044 KiB, score = 100

program classroom(input,output);
var
s,t,d,a:array[1..1000000] of longint;
f:array[1..1000001] of int64;
k:array[1..1000000] of int64;
n,m:longint;
z:longint;
procedure init;
var
i:longint;
begin
assign(input,'classroom.in');
assign(output,'classroom.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to n do
read(a[i]);
readln;
for i:=1 to m do readln(d[i],s[i],t[i]);
close(input);
randomize;
fillchar(f,sizeof(f),0);
z:=0;
fillchar(k,sizeof(k),0);
end;
function check(x:longint):boolean;
var
i:longint;
begin
if z<x then
for i:=z+1 to x do
begin
f[s[i]]:=f[s[i]]+d[i];
f[t[i]+1]:=f[t[i]+1]-d[i];
end;
if z>x then
for i:=x+1 to z do
begin
f[s[i]]:=f[s[i]]-d[i];
f[t[i]+1]:=f[t[i]+1]+d[i];
end;
z:=x;
k[1]:=f[1];
if k[1]>a[1] then exit(false);
for i:=2 to n do
begin
k[i]:=k[i-1]+f[i];
if k[i]>a[i] then exit(false);
end;
{ for i:=1 to n do
if k[i]>a[i] then exit(false);}
exit(true);
end;
procedure out_put(x:longint);
begin
writeln(x);
close(output);
halt;
end;
procedure work;
var
j,i,x:longint;
begin
j:=m;
if check(1)=false then
begin writeln(-1); out_put(1); end;
if check(m) then
begin
writeln(0);
close(output);
halt;
end else writeln(-1);
i:=0;
while true do
begin
x:=(j-i+1) div 2+i;
if check(x)=false then
begin
if (j-i=1) then out_put(j);
if (x-i=1) then out_put(x);
j:=x;
end else
begin
if (j-i=1) then out_put(j);
if (j-x=1) then out_put(j);
i:=x;
end;
if (i=j) then out_put(i);
end;
end;
begin
init;
work;
end.

sofa

#include <cstdio>
#include <cstring>
#define O 1000100

int n,m;
int r[O],d[O],s[O],t[O];
int pre[O];

int check(int x){
memset(pre,0,sizeof(pre));
for(int i=1;i<=x;i++){
pre[s[i]]+=d[i];
pre[t[i]+1]-=d[i];
}
int now=0;
for(int i=1;i<=n;i++){
now+=pre[i];
if(now>r[i])
return 0;
}
return 1;
}

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]);
int L=1,R=m,mid,ans=0;
while(L<R){
mid=(L+R)/2;
if(!check(mid)){
ans=mid;
R=mid;
}
else
L=mid+1;

}
if(ans==0)
printf("0");
else
printf("-1\n%d",ans);
return 0;
}

C++题解+代码
http://www.cnblogs.com/937337156Zhang/p/5697140.html

//输入很重要
//用 cin ，ios::sync_with_stdio(false)cin，和scanf的结果差别很大！！！！！！！！！
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

#define MAXN 1000001

int n, m;

int unc[MAXN];
int dunc[MAXN], sunc[MAXN], tunc[MAXN];
int twounc[MAXN];
int notu = -1;

inline int fin(int l, int r)
{
if (r <= l)return 0;
int i, j;
int mid = (l + r) / 2;
bool key = true;
//前缀和（简单而极其有效 6666）
memset(twounc, 0, sizeof(twounc));
for (j = 1; j <= mid; ++j)
{
twounc[sunc[j]] += dunc[j];
twounc[tunc[j] + 1] -= dunc[j];
}
int sum = 0;
for (i = 1; i <= n; ++i)
{
sum += twounc[i];
if (sum > unc[i])goto A1;
}
key = false;
A1:
if (key)
{
notu = mid;
fin(l, mid);
}
else fin(mid + 1, r);
return 0;
}

int main()
{
// ios::sync_with_stdio(false);
int i;
scanf("%d %d", &n, &m);
for (i = 1; i <= n; ++i)
{
scanf("%d", &unc[i]);
}
for (i = 1; i <= m; ++i)
{
scanf("%d %d %d", &dunc[i], &sunc[i], &tunc[i]);
}
fin(1, m);
if (notu != -1)
cout << -1 << endl << notu;
else cout << 0;
//system("pause");
return 0;
}

二分订单+前缀和+读入优化=完美！>_<

第一次独立的打对线段树！！！！！！！

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define INF 0x3f3f3f3f
using namespace std;
struct node{
int id,l,r,minin,lazy,numv;
}tree[4*1000000];
int n,m,num[1000005]={0},d,s,t;
void read(int &x){
char ch;
int f=1;
x=0;
ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
}
void build(int i,int l,int r){
tree[i].l=l;tree[i].r=r;
tree[i].lazy=0;tree[i].minin=INF;
tree[i].numv=0;
tree[i].id=i;
if(l==r){
num[l]=i;
return;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build((i<<1)+1,mid+1,r);
}
void change(int i,int v){
while(i>1){
if(tree[i].l==tree[i].r){
tree[i].minin=v;
}
int fa=i>>1;
int left=fa<<1,right=(fa<<1)+1;
tree[fa].minin=min(tree[fa].minin,tree[i].minin);
i=fa;
}
return;
}
int check(int v,int sta,int to,int i,int l,int r){
if(tree[i].lazy!=0&&l!=r){
int left=i<<1,right=(i<<1)+1,u=tree[i].lazy;
tree[left].minin-=u;tree[right].minin-=u;
tree[left].lazy+=u;tree[right].lazy+=u;
tree[i].lazy=0;
}
if(r<sta||l>to) return tree[i].minin;
if(l>=sta&&r<=to){
tree[i].minin-=v;
tree[i].lazy+=v;
return tree[i].minin;
}
else{
int mid=(l+r)>>1;
int tmp1=check(v,sta,to,i<<1,l,mid);
int tmp2=check(v,sta,to,(i<<1)+1,mid+1,r);
tree[i].minin=min(tmp1,tmp2);
return tree[i].minin;
}
}
int main(){
freopen("classroom7.in","r",stdin);
//freopen("classroom.out","w",stdout);
int i,r;
read(n);read(m);
build(1,1,n);
for(i=1;i<=n;i++){
read(r);
change(num[i],r);
}
for(i=1;i<=m;i++){
read(d);read(s);read(t);
int temp=check(d,s,t,1,1,n);
if(temp<0){
printf("-1\n%d",i);
return 0;
}
}
printf("0\n");
return 0;
}


二分法 二分订单编号
如果前mid个订单可行 l=mid+1
否则 r=mid
在这里特别注意边界的讨论 +1还是不加
（前mid可行 所以不可行的只在mid+1后）
（前mid不可行 不可行的可能包括mid 所以不-1）
判断前x个可不可行 用前缀和......
前缀和是个神奇的算法 但很好理解
订单从i=1到x循环 在pre[start[i]]加上订单i的天数 并在pre[end[i]+1]减去订单i的天数
开一个sum变量 表示当前正在使用的房间个数。
循环 i=1 到 n ，sum+=pre[i]
自然的，在start[i]天时就会加上所使用的房间，在end[i]+1天时就会自动减去它们
注意大数组开在开头 如果开在函数内 会出错
#include <cstdio>
#include <cstring>
#define Q 1000100

int n,m,r[Q],d[Q],s[Q],t[Q],pre[Q];

int g(){
char p=' ';int x=0;
while(!(p>='0'&&p<='9')) p=getchar();
while(p>='0'&&p<='9') x=x*10+p-'0',p=getchar();
return x;
}

int check(int x){
int sum=0;
memset(pre,0,sizeof(pre));
for(int i=1;i<=x;i++)
pre[s[i]]+=d[i],
pre[t[i]+1]-=d[i];
for(int i=1;i<=n;i++){
sum+=pre[i];
if(sum>r[i]) return 0;
}

return 1;
}

int main(){
freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
r[i]=g();
for(int i=1;i<=m;i++)
d[i]=g(),s[i]=g(),t[i]=g();
int L=1,R=m,mid,ans=0;
while(L<R){
mid=(L+R)/2;
if(check(mid)==0)
ans=mid,R=mid;
else
L=mid+1;
}
if(ans) printf("-1\n%d",ans);
else printf("0");
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 20080 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 20076 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 20076 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 20080 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 20076 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 20084 KiB, score = 5
测试数据 #6: Accepted, time = 156 ms, mem = 20080 KiB, score = 5
测试数据 #7: Accepted, time = 140 ms, mem = 20072 KiB, score = 5
测试数据 #8: Accepted, time = 171 ms, mem = 20080 KiB, score = 5
测试数据 #9: Accepted, time = 156 ms, mem = 20080 KiB, score = 5
测试数据 #10: Accepted, time = 140 ms, mem = 20080 KiB, score = 5
测试数据 #11: Accepted, time = 156 ms, mem = 20076 KiB, score = 5
测试数据 #12: Accepted, time = 140 ms, mem = 20080 KiB, score = 5
测试数据 #13: Accepted, time = 171 ms, mem = 20076 KiB, score = 5
测试数据 #14: Accepted, time = 1500 ms, mem = 20080 KiB, score = 5
测试数据 #15: Accepted, time = 1453 ms, mem = 20080 KiB, score = 5
测试数据 #16: Accepted, time = 1750 ms, mem = 20076 KiB, score = 5
测试数据 #17: Accepted, time = 1656 ms, mem = 20076 KiB, score = 5
测试数据 #18: Accepted, time = 1578 ms, mem = 20080 KiB, score = 5
测试数据 #19: Accepted, time = 1734 ms, mem = 20076 KiB, score = 5
Accepted, time = 10916 ms, mem = 20084 KiB, score = 100
代码
#include <cstring>
#include <cstdio>
int ans = 0,n,m,x[1000001],r[1000001],d[1000001],s[1000001],t[1000001];
inline void find(int L,int R) {
  if (R <= L) return;
  int mid = (L+R)/2;
  bool flag = true;
  memset(x,0,sizeof(x));
  for (int i = 1;i <= mid;i++) {
    x[s[i]] += d[i];
    x[t[i]+1] -= d[i];
  }
  int sum = 0;
  for (int i = 1;i <= n;i++) {
    sum += x[i];
    if (sum > r[i]) {
      flag = false;
      break;
    }
  }
  if (!flag) {
    ans = mid;
    find(L,mid);
  } else find(mid+1,R);
}
int main() {
  //freopen("classroom.in","r",stdin);
  //freopen("classroom.out","w",stdout);
  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]);
  find(1,m);
  if (!ans) printf("0");
  else printf("-1\n%d",ans);
  return 0;
}

顺便*安利*一下我个人的**博客**：
Haogram的博客：http://haogram.hol.es/
谢谢。