先二分一个答案 x, 然后通过差分来看有没有不满足的
- #include<bits/stdc++.h>
- #define pa pair<int,int>
- #define lowb(x) ((x)&(-(x)))
- #define REP(i,n0,n) for(i=n0;i<=n;i++)
- #define PER(i,n0,n) for(i=n;i>=n0;i--)
- #define MAX(a,b) ((a>b)?a:b)
- #define MIN(a,b) ((a<b)?a:b)
- #define CLR(a,x) memset(a,x,sizeof(a))
- #define rei register int
- using namespace std;
- typedef long long ll;
- const int maxn=1e6+5;
- inline ll rd(){
- ll x=0;char c=getchar();int neg=1;
- while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
- while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
- return x*neg;
- }
- int N,M,ask[maxn][3];
- int num[maxn],cnt[maxn];
- inline bool judge(int m){
- memset(cnt,0,sizeof(cnt));
- for(int i=1;i<=m;i++){
- cnt[ask[i][0]]+=ask[i][2],cnt[ask[i][1]+1]-=ask[i][2];
- }
- for(int i=1,j=0;i<=N;i++){
- j+=cnt[i];
- if(j>num[i]) return 0;
- }return 1;
- }
- int main(){
- //freopen(".in","r",stdin);
- rei i,j,k;
- N=rd(),M=rd();
- for(i=1;i<=N;i++) num[i]=rd();
- for(i=1;i<=M;i++){
- int a=rd(),b=rd(),c=rd();
- ask[i][0]=b,ask[i][1]=c,ask[i][2]=a;
- }
- int l=0,r=M,ans;
- while(l<=r){
- int m=l+r>>1;
- if(judge(m)) ans=m+1,l=m+1;
- else ans=m,r=m-1;
- }
- if(ans>M) printf("0\n");
- else{
- printf("-1\n%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2789162.html