【NOIP2012 提高组 day2】借教室
题解:
巧妙应用二分策略,再利用一下前缀和,差分的功能就OK
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n,m;
int r[MAXN];
int d[MAXN],s[MAXN],t[MAXN];
int cf[MAXN];
bool ok(int x){
memset(cf,0,sizeof(cf));
for(int i=1;i<=x;i++){
cf[s[i]]+=d[i];
cf[t[i]+1]-=d[i];
}
for(int i=1;i<=n;i++){
cf[i]+=cf[i-1];
if(cf[i]>r[i])
return 0;
}
return 1;
}
int main(){
cin>>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(ok(m)){
cout<<0;
return 0;
}
int L=1,R=m;
while(L<R){
int mid=(L+R)/2;
if(ok(mid))
L=mid+1;
else
R=mid;
}
cout<<-1<<endl<<R;
return 0;
}