1 条题解
-
1
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int n,m; int diff[1000011],need[1000011],rest[1000011],r[1000011],l[1000011],d[1000011]; bool isok(int x) { memset(diff,0,sizeof(diff)); for(int i=1;i<=x;i++) { diff[l[i]]+=d[i]; diff[r[i]+1]-=d[i]; } for(int i=1;i<=n;i++) { need[i]=need[i-1]+diff[i]; if(need[i]>rest[i])return 0; } return 1; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&rest[i]); for(int i=1;i<=m;i++)scanf("%d%d%d",&d[i],&l[i],&r[i]); int begin=1,end=m; if(isok(m)){cout<<"0";return 0;} while(begin<end) { int mid=(begin+end)/2; if(isok(mid))begin=mid+1; else end=mid; } cout<<"-1"<<endl<<begin; }
- 1
信息
- ID
- 42
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 5
- 标签
- 递交数
- 26
- 已通过
- 14
- 上传者