1 #include<bits/stdc++.h>
2 using namespace std;
3 #define maxn 1000000
4 #define inf 1<<30
5
6 int n,m,tot,num[maxn],q[maxn];
7 int sta[maxn],d[maxn],end[maxn];
8
9 bool check(int now)
10 {
11 tot=0;
12 for(int i=1;i<=n;i++) q[i]=0;
13 for(int i=1;i<=now;i++) q[sta[i]]+=d[i],q[end[i]+1]-=d[i];
14 for(int i=1;i<=n;i++)
15 {
16 tot+=q[i];
17 if(tot>num[i]) return false;
18 }
19 return true;
20 }
21
22 int main()
23 {
24 scanf("%d%d",&n,&m);
25 for(int i=1;i<=n;i++) scanf("%d",&num[i]);
26 for(int i=1;i<=m;i++) scanf("%d%d%d",&d[i],&sta[i],&end[i]);
27 int l=1,r=m;
28 while(l<=r)
29 {
30 int mid=(l+r)/2;
31 if(check(mid)) l=mid+1;
32 else r=mid-1;
33 }
34 if(l>m) printf("0
");
35 else printf("-1
%d
",l);
36 return 0;
37 }
二分
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=1000005;
4 int n,m,x,y,num,i;
5
6 struct Edge{
7 int l,r,w,f,mn;
8 }tree[maxn<<2];
9
10 char Cget;
11 inline void read(int &now)
12 {
13 now=0; Cget=getchar();
14 while(Cget>'9'||Cget<'0') Cget=getchar();
15 while(Cget>='0'&&Cget<='9') now=now*10+Cget-'0',Cget=getchar();
16 }
17
18 inline int min(int a,int b) { return a<b?a:b;}
19
20 inline void tree_down(int k)
21 {
22 tree[k<<1].f+=tree[k].f,tree[k<<1|1].f+=tree[k].f;
23 tree[k<<1].mn-=tree[k].f,tree[k<<1|1].mn-=tree[k].f;
24 tree[k].f=0;
25 }
26
27 void tree_build(int l,int r,int k)
28 {
29 tree[k].l=l,tree[k].r=r;
30 if(l==r)
31 {
32 read(tree[k].mn);
33 return ;
34 }
35 int mid=(l+r)>>1;
36 tree_build(l,mid,k<<1);
37 tree_build(mid+1,r,k<<1|1);
38 tree[k].mn=min(tree[k<<1].mn,tree[k<<1|1].mn);
39 }
40
41 void tree_change(int l,int r,int k,int to)
42 {
43 if(tree[k].l>=l&&tree[k].r<=r)
44 {
45 if(tree[k].mn<to)
46 {
47 printf("-1
%d
",i);
48 exit(0);
49 }
50 tree[k].mn-=to,tree[k].f+=to;
51 return ;
52 }
53 if(tree[k].f) tree_down(k);
54 int mid=(tree[k].l+tree[k].r)>>1;
55 if(r<=mid) tree_change(l,r,k<<1,to);
56 else if(l>mid) tree_change(l,r,k<<1|1,to);
57 else{
58 tree_change(l,mid,k<<1,to);
59 tree_change(mid+1,r,k<<1|1,to);
60 }
61 tree[k].mn=min(tree[k<<1].mn,tree[k<<1|1].mn);
62 }
63
64 int main()
65 {
66 read(n),read(m);
67 tree_build(1,n,1);
68 for(i=1;i<=m;i++)
69 {
70 read(num),read(x),read(y);
71 tree_change(x,y,1,num);
72 }
73 puts("0");
74 return 0;
75 }