// vaziat meshki-ghermeze !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Inf = 2242545357980376863LL;
const int N = 1e6 + 10;
ll lz[N << 2];
ll seg[N << 2];
void Apply(int id, ll x){
seg[id] += x;
lz[id] += x;
}
void Shift(int id){
Apply(id << 1, lz[id]);
Apply(id << 1 | 1, lz[id]);
lz[id] = 0;
}
void Add(int id, int l, int r, ll x, int L, int R){
if(r <= L || R <= l)
return ;
if(l <= L && R <= r){
Apply(id, x);
return ;
}
int mid = (L + R) >> 1;
Shift(id);
Add(id << 1, l, r, x, L, mid);
Add(id<<1|1, l, r, x, mid, R);
seg[id] = max(seg[id << 1], seg[id << 1|1]);
}
ll Get(int id, int l, int r, int L, int R){
if(r <= L || R <= l) return -Inf;
if(l <= L && R <= r) return seg[id];
Shift(id);
int mid = (L + R) >> 1;
return max(
Get(id << 1, l, r, L, mid),
Get(id<<1|1, l, r, mid, R)
);
}
int n, m;
int A[N], B[N];
int S[N], T[N];
int P[N], Q[N];
vector<pll> H[N];
void Fix(int idx){
int nw = Get(1, idx, idx + 1, 0, N);
int fut = Get(1, 0, idx + 1, 0, N);
Add(1, idx, idx + 1, fut - nw, 0, N);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> A[i] >> S[i] >> P[i];
for(int i = 1; i <= m; i++)
cin >> B[i] >> T[i] >> Q[i];
for(int i = 1; i <= n; i++) A[i] += A[i - 1];
for(int i = 1; i <= m; i++) B[i] += B[i - 1];
for(int i = 1; i <= n; i++){
int idx = upper_bound(B, B + m + 1, S[i] - A[i]) - B;
if(idx == 0) continue;
H[i].pb({idx, P[i]});
}
ll ans = 0;
for(int i = 1; i <= m; i++){
int idx = upper_bound(A, A + n + 1, T[i] - B[i]) - A;
if(idx == 0) continue;
ans += Q[i];
H[idx].pb({i, -Q[i]});
}
for(int i = 1; i <= n; i++){
for(auto [r, v] : H[i])
Fix(r);
for(auto [r, v] : H[i])
Add(1, 0, r, v, 0, N);
}
cout << ans + Get(1, 0, m + 1, 0, N) << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
295 ms |
35400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
295 ms |
35400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
295 ms |
35400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
