1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e6;
int lazy[4*N],mv[4*N];
void read(int &x)
{
char c=getchar();
x=0;
while (!(c>='0'&&c<='9'||c=='-')) c=getchar();
int f=0;
if (c=='-') {
f=1;
c=getchar();
}
while (c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
if (f) x=-x;
}
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
void push_up(int rt)
{
mv[rt]=min(mv[rt<<1],mv[rt<<1|1]);
}
void build(int l,int r,int rt)
{
if (l==r) {
read(mv[rt]);
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
push_up(rt);
}
void push_down(int rt)
{
lazy[rt<<1]+=lazy[rt];
mv[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
mv[rt<<1|1]+=lazy[rt];
lazy[rt]=0;
}
bool update(int l,int r,int rt,int L,int R,int del)
{
if (L<=l&&r<=R) {
lazy[rt]+=del;
mv[rt]+=del;
if (mv[rt]<0) return false;
else return true;
}
push_down(rt);
int m=(l+r)>>1;
bool res=true;
if (L<=m) res&=update(lson,L,R,del);
if (!res) return false;
if (m<R) res&=update(rson,L,R,del);
push_up(rt);
return res;
}
int n,m;
int check()
{
for (int i=1; i<=m; i++) {
int d,s,t;
read(d);
read(s);
read(t);
if (!update(1,n,1,s,t,-d)) return i;
}
return m+1;
}
int main()
{
read(n);
read(m);
build(1,n,1);
int ans=check();
if (ans>m) puts("0");
else printf("-1\n%d\n",ans);
return 0;
}
|
