这道题要读入优化

#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 条评论

  • 1

信息

ID
1782
难度
8
分类
模拟 | 其他 | 二分查找数据结构 | 线段树 点击显示
标签
递交数
8241
已通过
1234
通过率
15%
被复制
12
上传者