#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<int> vi;
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define rep(i,a,b) for(int i=a; i<=b; i++)
const int N=1e6+1;
int n, m;
ll a[N], b[N], p[N], q[N], s[N], t[N];
map<int,ll> qu[N];
bool st[4*N];
ll seg[4*N];
void push(int x, int lx, int rx){
if(rx-lx==1) return;
if(st[x]){
seg[2*x+1]=seg[2*x+2]=seg[x];
st[2*x+1]=st[2*x+2]=1;
seg[x]=0;
st[x]=0;
return;
}
seg[2*x+1]+=seg[x];
seg[2*x+2]+=seg[x];
seg[x]=0;
}
void add(int l, int r, int x, int lx, int rx, ll v){
// cout << "add " << l << r << " " << v << "\n";
push(x, lx, rx);
if(lx>=l && rx<=r){
seg[x]+=v;
return;
}
if(lx>=r || rx<=l) return;
int mid=(lx+rx)/2;
add(l, r, 2*x+1, lx, mid, v);
add(l, r, 2*x+2, mid, rx, v);
}
void add(int l, int r, ll v){
add(l, r, 0, 0, m+1, v);
}
void assign(int l, int r, ll v, int x, int lx, int rx){
push(x, lx, rx);
if(lx>=l && rx<=r){
// cout << "seg " << lx << " " << rx << " = " << v << "\n";
seg[x]=v;
st[x]=1;
return;
}
if(lx>=r || rx<=l) return;
int mid=(lx+rx)/2;
assign(l, r, v, 2*x+1, lx, mid);
assign(l, r, v, 2*x+2, mid, rx);
}
void assign(int l, int r, ll v){
if(r<=l) return;
assign(l, r, v, 0, 0, m+1);
}
void assign(int i, ll v){
assign(i, i+1, v);
}
ll qry(int i, int x, int lx, int rx){
if(rx-lx==1) return seg[x];
push(x, lx, rx);
int mid=(lx+rx)/2;
if(i<mid) return qry(i, 2*x+1, lx, mid);
return qry(i, 2*x+2, mid, rx);
}
ll qry(int i){
return qry(i, 0, 0, m+1);
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
ll ans=0;
vector<vi> pts;
vector<ll> A(n+1), B(m+1);
rep(i,1,n){
cin >> a[i] >> s[i] >> p[i];
A[i]=A[i-1]+a[i];
}
A.erase(A.begin());
rep(i,1,m){
cin >> b[i] >> t[i] >> q[i];
B[i]=B[i-1]+b[i];
int j=upper_bound(all(A), t[i]-B[i])-A.begin();
if(B[i]<=t[i]) qu[j][i]+=q[i];
}
B.erase(B.begin());
rep(i,1,n){
int j=upper_bound(all(B), s[i]-A[i-1])-B.begin();
if(A[i-1]<=s[i]){
ans+=p[i];
qu[i-1][j+1]-=p[i];
}
}
rep(i,0,n){
vector<pii> pts;
for(auto p:qu[i]) pts.push_back(p);
reverse(all(pts));
// cout << "x " << i << ":\n";
for(auto p:pts){
int y=p.f;
int v=p.s;
// cout << y << " " << v << "\n";
add(y, m+1, v);
// rep(i,0,m) cout << qry(i) << " ";
// cout << "\n";
if(i!=n){
int prv=qry(y-1);
int j=y-1;
for(int k=19; k>=0; k--){
if(j+(1<<k)<=m && qry(j+(1<<k))<prv) j+=(1<<k);
}
j++;
assign(y, j, prv);
// rep(i,0,m) cout << qry(i) << " ";
// cout << "\n";
}
}
}
cout << ans+qry(m);
}
// A: (x, <=y)
// B: (x, >=y)
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
920 ms |
92904 KB |
Output is correct |
2 |
Correct |
1026 ms |
95892 KB |
Output is correct |
3 |
Correct |
404 ms |
105612 KB |
Output is correct |
4 |
Correct |
694 ms |
85580 KB |
Output is correct |
5 |
Correct |
32 ms |
47288 KB |
Output is correct |
6 |
Correct |
1039 ms |
96164 KB |
Output is correct |
7 |
Correct |
242 ms |
78472 KB |
Output is correct |
8 |
Correct |
133 ms |
73108 KB |
Output is correct |
9 |
Correct |
465 ms |
106564 KB |
Output is correct |
10 |
Correct |
739 ms |
84336 KB |
Output is correct |
11 |
Correct |
321 ms |
100036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47316 KB |
Output is correct |
2 |
Correct |
30 ms |
47316 KB |
Output is correct |
3 |
Correct |
31 ms |
47292 KB |
Output is correct |
4 |
Correct |
29 ms |
47280 KB |
Output is correct |
5 |
Correct |
31 ms |
47316 KB |
Output is correct |
6 |
Correct |
39 ms |
47332 KB |
Output is correct |
7 |
Correct |
36 ms |
47284 KB |
Output is correct |
8 |
Correct |
35 ms |
47328 KB |
Output is correct |
9 |
Correct |
37 ms |
47336 KB |
Output is correct |
10 |
Correct |
32 ms |
47324 KB |
Output is correct |
11 |
Correct |
32 ms |
47308 KB |
Output is correct |
12 |
Correct |
28 ms |
47240 KB |
Output is correct |
13 |
Correct |
30 ms |
47336 KB |
Output is correct |
14 |
Correct |
30 ms |
47304 KB |
Output is correct |
15 |
Correct |
33 ms |
47292 KB |
Output is correct |
16 |
Correct |
29 ms |
47300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47316 KB |
Output is correct |
2 |
Correct |
30 ms |
47316 KB |
Output is correct |
3 |
Correct |
31 ms |
47292 KB |
Output is correct |
4 |
Correct |
29 ms |
47280 KB |
Output is correct |
5 |
Correct |
31 ms |
47316 KB |
Output is correct |
6 |
Correct |
39 ms |
47332 KB |
Output is correct |
7 |
Correct |
36 ms |
47284 KB |
Output is correct |
8 |
Correct |
35 ms |
47328 KB |
Output is correct |
9 |
Correct |
37 ms |
47336 KB |
Output is correct |
10 |
Correct |
32 ms |
47324 KB |
Output is correct |
11 |
Correct |
32 ms |
47308 KB |
Output is correct |
12 |
Correct |
28 ms |
47240 KB |
Output is correct |
13 |
Correct |
30 ms |
47336 KB |
Output is correct |
14 |
Correct |
30 ms |
47304 KB |
Output is correct |
15 |
Correct |
33 ms |
47292 KB |
Output is correct |
16 |
Correct |
29 ms |
47300 KB |
Output is correct |
17 |
Correct |
33 ms |
47832 KB |
Output is correct |
18 |
Correct |
27 ms |
47856 KB |
Output is correct |
19 |
Correct |
39 ms |
47932 KB |
Output is correct |
20 |
Correct |
37 ms |
47712 KB |
Output is correct |
21 |
Correct |
40 ms |
47840 KB |
Output is correct |
22 |
Correct |
41 ms |
47800 KB |
Output is correct |
23 |
Correct |
41 ms |
47676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47316 KB |
Output is correct |
2 |
Correct |
30 ms |
47316 KB |
Output is correct |
3 |
Correct |
31 ms |
47292 KB |
Output is correct |
4 |
Correct |
29 ms |
47280 KB |
Output is correct |
5 |
Correct |
31 ms |
47316 KB |
Output is correct |
6 |
Correct |
39 ms |
47332 KB |
Output is correct |
7 |
Correct |
36 ms |
47284 KB |
Output is correct |
8 |
Correct |
35 ms |
47328 KB |
Output is correct |
9 |
Correct |
37 ms |
47336 KB |
Output is correct |
10 |
Correct |
32 ms |
47324 KB |
Output is correct |
11 |
Correct |
32 ms |
47308 KB |
Output is correct |
12 |
Correct |
28 ms |
47240 KB |
Output is correct |
13 |
Correct |
30 ms |
47336 KB |
Output is correct |
14 |
Correct |
30 ms |
47304 KB |
Output is correct |
15 |
Correct |
33 ms |
47292 KB |
Output is correct |
16 |
Correct |
29 ms |
47300 KB |
Output is correct |
17 |
Correct |
33 ms |
47832 KB |
Output is correct |
18 |
Correct |
27 ms |
47856 KB |
Output is correct |
19 |
Correct |
39 ms |
47932 KB |
Output is correct |
20 |
Correct |
37 ms |
47712 KB |
Output is correct |
21 |
Correct |
40 ms |
47840 KB |
Output is correct |
22 |
Correct |
41 ms |
47800 KB |
Output is correct |
23 |
Correct |
41 ms |
47676 KB |
Output is correct |
24 |
Correct |
657 ms |
95544 KB |
Output is correct |
25 |
Correct |
997 ms |
96592 KB |
Output is correct |
26 |
Correct |
678 ms |
96132 KB |
Output is correct |
27 |
Correct |
740 ms |
93320 KB |
Output is correct |
28 |
Correct |
837 ms |
99392 KB |
Output is correct |
29 |
Correct |
391 ms |
103588 KB |
Output is correct |
30 |
Correct |
1908 ms |
99776 KB |
Output is correct |
31 |
Correct |
461 ms |
79084 KB |
Output is correct |
32 |
Correct |
190 ms |
71304 KB |
Output is correct |
33 |
Correct |
1234 ms |
87184 KB |
Output is correct |
34 |
Correct |
1319 ms |
99684 KB |
Output is correct |
35 |
Correct |
1995 ms |
93544 KB |
Output is correct |
36 |
Correct |
1853 ms |
93276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47316 KB |
Output is correct |
2 |
Correct |
30 ms |
47316 KB |
Output is correct |
3 |
Correct |
31 ms |
47292 KB |
Output is correct |
4 |
Correct |
29 ms |
47280 KB |
Output is correct |
5 |
Correct |
31 ms |
47316 KB |
Output is correct |
6 |
Correct |
39 ms |
47332 KB |
Output is correct |
7 |
Correct |
36 ms |
47284 KB |
Output is correct |
8 |
Correct |
35 ms |
47328 KB |
Output is correct |
9 |
Correct |
37 ms |
47336 KB |
Output is correct |
10 |
Correct |
32 ms |
47324 KB |
Output is correct |
11 |
Correct |
32 ms |
47308 KB |
Output is correct |
12 |
Correct |
28 ms |
47240 KB |
Output is correct |
13 |
Correct |
30 ms |
47336 KB |
Output is correct |
14 |
Correct |
30 ms |
47304 KB |
Output is correct |
15 |
Correct |
33 ms |
47292 KB |
Output is correct |
16 |
Correct |
29 ms |
47300 KB |
Output is correct |
17 |
Correct |
33 ms |
47832 KB |
Output is correct |
18 |
Correct |
27 ms |
47856 KB |
Output is correct |
19 |
Correct |
39 ms |
47932 KB |
Output is correct |
20 |
Correct |
37 ms |
47712 KB |
Output is correct |
21 |
Correct |
40 ms |
47840 KB |
Output is correct |
22 |
Correct |
41 ms |
47800 KB |
Output is correct |
23 |
Correct |
41 ms |
47676 KB |
Output is correct |
24 |
Correct |
657 ms |
95544 KB |
Output is correct |
25 |
Correct |
997 ms |
96592 KB |
Output is correct |
26 |
Correct |
678 ms |
96132 KB |
Output is correct |
27 |
Correct |
740 ms |
93320 KB |
Output is correct |
28 |
Correct |
837 ms |
99392 KB |
Output is correct |
29 |
Correct |
391 ms |
103588 KB |
Output is correct |
30 |
Correct |
1908 ms |
99776 KB |
Output is correct |
31 |
Correct |
461 ms |
79084 KB |
Output is correct |
32 |
Correct |
190 ms |
71304 KB |
Output is correct |
33 |
Correct |
1234 ms |
87184 KB |
Output is correct |
34 |
Correct |
1319 ms |
99684 KB |
Output is correct |
35 |
Correct |
1995 ms |
93544 KB |
Output is correct |
36 |
Correct |
1853 ms |
93276 KB |
Output is correct |
37 |
Correct |
837 ms |
99024 KB |
Output is correct |
38 |
Correct |
876 ms |
96408 KB |
Output is correct |
39 |
Correct |
729 ms |
87448 KB |
Output is correct |
40 |
Correct |
594 ms |
87980 KB |
Output is correct |
41 |
Correct |
25 ms |
47360 KB |
Output is correct |
42 |
Incorrect |
1840 ms |
102980 KB |
Output isn't correct |
43 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47316 KB |
Output is correct |
2 |
Correct |
30 ms |
47316 KB |
Output is correct |
3 |
Correct |
31 ms |
47292 KB |
Output is correct |
4 |
Correct |
29 ms |
47280 KB |
Output is correct |
5 |
Correct |
31 ms |
47316 KB |
Output is correct |
6 |
Correct |
39 ms |
47332 KB |
Output is correct |
7 |
Correct |
36 ms |
47284 KB |
Output is correct |
8 |
Correct |
35 ms |
47328 KB |
Output is correct |
9 |
Correct |
37 ms |
47336 KB |
Output is correct |
10 |
Correct |
32 ms |
47324 KB |
Output is correct |
11 |
Correct |
32 ms |
47308 KB |
Output is correct |
12 |
Correct |
28 ms |
47240 KB |
Output is correct |
13 |
Correct |
30 ms |
47336 KB |
Output is correct |
14 |
Correct |
30 ms |
47304 KB |
Output is correct |
15 |
Correct |
33 ms |
47292 KB |
Output is correct |
16 |
Correct |
29 ms |
47300 KB |
Output is correct |
17 |
Correct |
33 ms |
47832 KB |
Output is correct |
18 |
Correct |
27 ms |
47856 KB |
Output is correct |
19 |
Correct |
39 ms |
47932 KB |
Output is correct |
20 |
Correct |
37 ms |
47712 KB |
Output is correct |
21 |
Correct |
40 ms |
47840 KB |
Output is correct |
22 |
Correct |
41 ms |
47800 KB |
Output is correct |
23 |
Correct |
41 ms |
47676 KB |
Output is correct |
24 |
Correct |
657 ms |
95544 KB |
Output is correct |
25 |
Correct |
997 ms |
96592 KB |
Output is correct |
26 |
Correct |
678 ms |
96132 KB |
Output is correct |
27 |
Correct |
740 ms |
93320 KB |
Output is correct |
28 |
Correct |
837 ms |
99392 KB |
Output is correct |
29 |
Correct |
391 ms |
103588 KB |
Output is correct |
30 |
Correct |
1908 ms |
99776 KB |
Output is correct |
31 |
Correct |
461 ms |
79084 KB |
Output is correct |
32 |
Correct |
190 ms |
71304 KB |
Output is correct |
33 |
Correct |
1234 ms |
87184 KB |
Output is correct |
34 |
Correct |
1319 ms |
99684 KB |
Output is correct |
35 |
Correct |
1995 ms |
93544 KB |
Output is correct |
36 |
Correct |
1853 ms |
93276 KB |
Output is correct |
37 |
Correct |
837 ms |
99024 KB |
Output is correct |
38 |
Correct |
876 ms |
96408 KB |
Output is correct |
39 |
Correct |
729 ms |
87448 KB |
Output is correct |
40 |
Correct |
594 ms |
87980 KB |
Output is correct |
41 |
Correct |
25 ms |
47360 KB |
Output is correct |
42 |
Incorrect |
1840 ms |
102980 KB |
Output isn't correct |
43 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
920 ms |
92904 KB |
Output is correct |
2 |
Correct |
1026 ms |
95892 KB |
Output is correct |
3 |
Correct |
404 ms |
105612 KB |
Output is correct |
4 |
Correct |
694 ms |
85580 KB |
Output is correct |
5 |
Correct |
32 ms |
47288 KB |
Output is correct |
6 |
Correct |
1039 ms |
96164 KB |
Output is correct |
7 |
Correct |
242 ms |
78472 KB |
Output is correct |
8 |
Correct |
133 ms |
73108 KB |
Output is correct |
9 |
Correct |
465 ms |
106564 KB |
Output is correct |
10 |
Correct |
739 ms |
84336 KB |
Output is correct |
11 |
Correct |
321 ms |
100036 KB |
Output is correct |
12 |
Correct |
24 ms |
47316 KB |
Output is correct |
13 |
Correct |
30 ms |
47316 KB |
Output is correct |
14 |
Correct |
31 ms |
47292 KB |
Output is correct |
15 |
Correct |
29 ms |
47280 KB |
Output is correct |
16 |
Correct |
31 ms |
47316 KB |
Output is correct |
17 |
Correct |
39 ms |
47332 KB |
Output is correct |
18 |
Correct |
36 ms |
47284 KB |
Output is correct |
19 |
Correct |
35 ms |
47328 KB |
Output is correct |
20 |
Correct |
37 ms |
47336 KB |
Output is correct |
21 |
Correct |
32 ms |
47324 KB |
Output is correct |
22 |
Correct |
32 ms |
47308 KB |
Output is correct |
23 |
Correct |
28 ms |
47240 KB |
Output is correct |
24 |
Correct |
30 ms |
47336 KB |
Output is correct |
25 |
Correct |
30 ms |
47304 KB |
Output is correct |
26 |
Correct |
33 ms |
47292 KB |
Output is correct |
27 |
Correct |
29 ms |
47300 KB |
Output is correct |
28 |
Correct |
33 ms |
47832 KB |
Output is correct |
29 |
Correct |
27 ms |
47856 KB |
Output is correct |
30 |
Correct |
39 ms |
47932 KB |
Output is correct |
31 |
Correct |
37 ms |
47712 KB |
Output is correct |
32 |
Correct |
40 ms |
47840 KB |
Output is correct |
33 |
Correct |
41 ms |
47800 KB |
Output is correct |
34 |
Correct |
41 ms |
47676 KB |
Output is correct |
35 |
Correct |
657 ms |
95544 KB |
Output is correct |
36 |
Correct |
997 ms |
96592 KB |
Output is correct |
37 |
Correct |
678 ms |
96132 KB |
Output is correct |
38 |
Correct |
740 ms |
93320 KB |
Output is correct |
39 |
Correct |
837 ms |
99392 KB |
Output is correct |
40 |
Correct |
391 ms |
103588 KB |
Output is correct |
41 |
Correct |
1908 ms |
99776 KB |
Output is correct |
42 |
Correct |
461 ms |
79084 KB |
Output is correct |
43 |
Correct |
190 ms |
71304 KB |
Output is correct |
44 |
Correct |
1234 ms |
87184 KB |
Output is correct |
45 |
Correct |
1319 ms |
99684 KB |
Output is correct |
46 |
Correct |
1995 ms |
93544 KB |
Output is correct |
47 |
Correct |
1853 ms |
93276 KB |
Output is correct |
48 |
Correct |
837 ms |
99024 KB |
Output is correct |
49 |
Correct |
876 ms |
96408 KB |
Output is correct |
50 |
Correct |
729 ms |
87448 KB |
Output is correct |
51 |
Correct |
594 ms |
87980 KB |
Output is correct |
52 |
Correct |
25 ms |
47360 KB |
Output is correct |
53 |
Incorrect |
1840 ms |
102980 KB |
Output isn't correct |
54 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
920 ms |
92904 KB |
Output is correct |
2 |
Correct |
1026 ms |
95892 KB |
Output is correct |
3 |
Correct |
404 ms |
105612 KB |
Output is correct |
4 |
Correct |
694 ms |
85580 KB |
Output is correct |
5 |
Correct |
32 ms |
47288 KB |
Output is correct |
6 |
Correct |
1039 ms |
96164 KB |
Output is correct |
7 |
Correct |
242 ms |
78472 KB |
Output is correct |
8 |
Correct |
133 ms |
73108 KB |
Output is correct |
9 |
Correct |
465 ms |
106564 KB |
Output is correct |
10 |
Correct |
739 ms |
84336 KB |
Output is correct |
11 |
Correct |
321 ms |
100036 KB |
Output is correct |
12 |
Correct |
24 ms |
47316 KB |
Output is correct |
13 |
Correct |
30 ms |
47316 KB |
Output is correct |
14 |
Correct |
31 ms |
47292 KB |
Output is correct |
15 |
Correct |
29 ms |
47280 KB |
Output is correct |
16 |
Correct |
31 ms |
47316 KB |
Output is correct |
17 |
Correct |
39 ms |
47332 KB |
Output is correct |
18 |
Correct |
36 ms |
47284 KB |
Output is correct |
19 |
Correct |
35 ms |
47328 KB |
Output is correct |
20 |
Correct |
37 ms |
47336 KB |
Output is correct |
21 |
Correct |
32 ms |
47324 KB |
Output is correct |
22 |
Correct |
32 ms |
47308 KB |
Output is correct |
23 |
Correct |
28 ms |
47240 KB |
Output is correct |
24 |
Correct |
30 ms |
47336 KB |
Output is correct |
25 |
Correct |
30 ms |
47304 KB |
Output is correct |
26 |
Correct |
33 ms |
47292 KB |
Output is correct |
27 |
Correct |
29 ms |
47300 KB |
Output is correct |
28 |
Correct |
33 ms |
47832 KB |
Output is correct |
29 |
Correct |
27 ms |
47856 KB |
Output is correct |
30 |
Correct |
39 ms |
47932 KB |
Output is correct |
31 |
Correct |
37 ms |
47712 KB |
Output is correct |
32 |
Correct |
40 ms |
47840 KB |
Output is correct |
33 |
Correct |
41 ms |
47800 KB |
Output is correct |
34 |
Correct |
41 ms |
47676 KB |
Output is correct |
35 |
Correct |
657 ms |
95544 KB |
Output is correct |
36 |
Correct |
997 ms |
96592 KB |
Output is correct |
37 |
Correct |
678 ms |
96132 KB |
Output is correct |
38 |
Correct |
740 ms |
93320 KB |
Output is correct |
39 |
Correct |
837 ms |
99392 KB |
Output is correct |
40 |
Correct |
391 ms |
103588 KB |
Output is correct |
41 |
Correct |
1908 ms |
99776 KB |
Output is correct |
42 |
Correct |
461 ms |
79084 KB |
Output is correct |
43 |
Correct |
190 ms |
71304 KB |
Output is correct |
44 |
Correct |
1234 ms |
87184 KB |
Output is correct |
45 |
Correct |
1319 ms |
99684 KB |
Output is correct |
46 |
Correct |
1995 ms |
93544 KB |
Output is correct |
47 |
Correct |
1853 ms |
93276 KB |
Output is correct |
48 |
Correct |
837 ms |
99024 KB |
Output is correct |
49 |
Correct |
876 ms |
96408 KB |
Output is correct |
50 |
Correct |
729 ms |
87448 KB |
Output is correct |
51 |
Correct |
594 ms |
87980 KB |
Output is correct |
52 |
Correct |
25 ms |
47360 KB |
Output is correct |
53 |
Incorrect |
1840 ms |
102980 KB |
Output isn't correct |
54 |
Halted |
0 ms |
0 KB |
- |