#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;
template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );
int n, m;
vector<int> pSA, pSB, p, q;
vector<LL> s, t;
struct It {
vector<LL> sum;
vector<bool> lz;
It(int nNode) { sum.assign(nNode, 0); lz.assign(nNode, false); }
void trueVal(int i, int Left, int Right) {
if (!lz[i]) return ;
sum[i] = 0;
if (Left != Right) lz[i << 1] = lz[i << 1 | 1] = lz[i];
lz[i] = false;
}
void upd(int l, int r, int i = 1, int Left = 0, int Right = m) {
trueVal(i, Left, Right);
if (r < Left || Right < l) return ;
if (l <= Left && Right <= r) {
lz[i] = true; trueVal(i, Left, Right);
return ;
}
int Mid = (Left + Right) >> 1;
upd(l, r, i << 1, Left, Mid);
upd(l, r, i << 1 | 1, Mid + 1, Right);
sum[i] = sum[i << 1] + sum[i << 1 | 1];
}
void add(int pos, LL val, int i = 1, int Left = 0, int Right = m) {
trueVal(i, Left, Right);
if (pos < Left || Right < pos) return ;
if (Left == Right) {
sum[i] += val;
return ;
}
int Mid = (Left + Right) >> 1;
add(pos, val, i << 1, Left, Mid);
add(pos, val, i << 1 | 1, Mid + 1, Right);
sum[i] = sum[i << 1] + sum[i << 1 | 1];
}
int findPos(int l, LL &cur, int i = 1, int Left = 0, int Right = m) {
trueVal(i, Left, Right);
if (Right < l) return m + 1;
if (l <= Left && sum[i] < cur) {
cur -= sum[i];
return m + 1;
}
if (Left == Right) return Left;
int Mid = (Left + Right) >> 1;
int tmp = findPos(l, cur, i << 1, Left, Mid);
if (tmp != m + 1) return tmp;
else return findPos(l, cur, i << 1 | 1, Mid + 1, Right);
}
LL get(int l, int r, int i = 1, int Left = 0, int Right = m) {
trueVal(i, Left, Right);
if (r < Left || Right < l) return 0;
if (l <= Left && Right <= r) return sum[i];
int Mid = (Left + Right) >> 1;
return get(l, r, i << 1, Left, Mid) + get(l, r, i << 1 | 1, Mid + 1, Right);
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef FourLeafClover
freopen("input", "r", stdin);
#endif // FourLeafCLover
cin >> n >> m;
pSA.assign(n + 1, 0);
pSB.assign(m + 1, 0);
s.assign(n + 1, 0);
t.assign(m + 1, 0);
p.assign(n + 1, 0);
q.assign(m + 1, 0);
for (int i = 1; i <= n; ++i) {
cin >> pSA[i] >> s[i] >> p[i];
pSA[i] += pSA[i - 1];
}
for (int i = 1; i <= m; ++i) {
cin >> pSB[i] >> t[i] >> q[i];
pSB[i] += pSB[i - 1];
}
vector<int> mxI(m + 1);
vector<vector<int> > changeMxI(n + 1);
for (int j = 0; j <= m; ++j) {
mxI[j] = (int)(upper_bound(all(pSA), t[j] - pSB[j]) - pSA.begin() ) - 1;
if (mxI[j] + 1 <= n) changeMxI[ mxI[j] + 1 ].emplace_back(j);
}
It it( (m + 5) << 2);
auto upd = [&](int pos) {
LL tmp = it.get(pos, pos);
if (tmp >= 0) return ;
tmp = -tmp;
int r = it.findPos(pos + 1, tmp);
it.add(r, it.get(pos, r - 1) );
it.upd(pos, r - 1);
};
for (int i = 1; i <= n; ++i) {
int mxJ = (int)(upper_bound(all(pSB), s[i] - pSA[i]) - pSB.begin() ) - 1;
vector<int> tmp;
if (mxJ >= 0) {
it.add(0, p[i]); tmp.emplace_back(0);
if (mxJ < m) {
it.add(mxJ + 1, -p[i]);
tmp.emplace_back(mxJ + 1);
}
}
for (auto j : changeMxI[i]) {
it.add(j, q[j]);
tmp.emplace_back(j);
}
sort(all(tmp) ); reverse(all(tmp) );
for (int j : tmp) upd(j);
}
LL ans = it.get(0, m);
for (int j = 0; j <= m; ++j) ans += mxI[j] < n ? 0 : q[j];
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
