//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct obj{
ll t, lim, val;
obj(){t = lim = val = 0;}
obj(ll x){t = x, lim = 0, val = 0;}
} a[maxn], b[maxn];
vector<int> upd[maxn];
const ll inf = 1LL<<60;
int main() {
io
int n, m;
cin >> n >> m;
for (int i = 0;i < n;i++) {
cin >> a[i].t >> a[i].lim >> a[i].val;
if (i) a[i].t += a[i-1].t;
}
for (int i = 0;i < m;i++) {
cin >> b[i].t >> b[i].lim >> b[i].val;
if (i) b[i].t += b[i-1].t;
}
for (int i = 0;i < n;i++) {
if (a[i].t > a[i].lim) {
a[i].val = 0;
} else {
int ind = upper_bound(b, b + m, obj(a[i].lim - a[i].t), [&] (obj x, obj y){return x.t < y.t;}) - b;
upd[ind].push_back(i);
}
}
map<int, ll> mp; //difference array of g
vector<int> neg;
auto pref = [&] () {
vector<int> val;
for (int p:neg) {
if (mp[p] >= 0) continue;
auto it = mp.upper_bound(p);
ll x = -mp[p];
mp[p] = 0;
val.push_back(p);
while (it != mp.end()) {
if (it->ss > x) {
it->ss -= x;
break;
} else {
if (it->ss >= 0) {
x -= it->ss;
it->ss = 0;
val.push_back(it->ff);
} else {
it->ss -= x;
x = 0;
break;
}
}
it = next(it);
}
}
for (auto i:val) mp.erase(mp.find(i));
neg.clear();
};
auto ch = [&] (int p, ll x) {
mp[p] += x;
if (mp[p] < 0 && p) {
neg.push_back(p);
}
};
for (int i = 0;i < m;i++) {
if (b[i].t <= b[i].lim) {
int ind = upper_bound(a, a + n, obj(b[i].lim - b[i].t), [&] (obj x, obj y){return x.t < y.t;}) - a;
ch(0, b[i].val);
ch(ind, -b[i].val);
}
for (int j:upd[i]) {
ch(j, a[j].val);
a[j].val = 0;
}
pref();
//debug(i);
//for (auto j:mp) debug(j.ff, j.ss);
}
ll ans = 0;
for (int i = 0;i < n;i++) ans += a[i].val;
for (auto i:mp) {
if (i.ff < n) ans += i.ss;
}
cout << ans << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
197 ms |
31684 KB |
Output is correct |
2 |
Correct |
264 ms |
40860 KB |
Output is correct |
3 |
Correct |
181 ms |
28828 KB |
Output is correct |
4 |
Incorrect |
176 ms |
31808 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
14284 KB |
Output is correct |
2 |
Correct |
6 ms |
14368 KB |
Output is correct |
3 |
Correct |
6 ms |
14284 KB |
Output is correct |
4 |
Correct |
7 ms |
14284 KB |
Output is correct |
5 |
Incorrect |
6 ms |
14400 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
14284 KB |
Output is correct |
2 |
Correct |
6 ms |
14368 KB |
Output is correct |
3 |
Correct |
6 ms |
14284 KB |
Output is correct |
4 |
Correct |
7 ms |
14284 KB |
Output is correct |
5 |
Incorrect |
6 ms |
14400 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
14284 KB |
Output is correct |
2 |
Correct |
6 ms |
14368 KB |
Output is correct |
3 |
Correct |
6 ms |
14284 KB |
Output is correct |
4 |
Correct |
7 ms |
14284 KB |
Output is correct |
5 |
Incorrect |
6 ms |
14400 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
14284 KB |
Output is correct |
2 |
Correct |
6 ms |
14368 KB |
Output is correct |
3 |
Correct |
6 ms |
14284 KB |
Output is correct |
4 |
Correct |
7 ms |
14284 KB |
Output is correct |
5 |
Incorrect |
6 ms |
14400 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
14284 KB |
Output is correct |
2 |
Correct |
6 ms |
14368 KB |
Output is correct |
3 |
Correct |
6 ms |
14284 KB |
Output is correct |
4 |
Correct |
7 ms |
14284 KB |
Output is correct |
5 |
Incorrect |
6 ms |
14400 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
197 ms |
31684 KB |
Output is correct |
2 |
Correct |
264 ms |
40860 KB |
Output is correct |
3 |
Correct |
181 ms |
28828 KB |
Output is correct |
4 |
Incorrect |
176 ms |
31808 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
197 ms |
31684 KB |
Output is correct |
2 |
Correct |
264 ms |
40860 KB |
Output is correct |
3 |
Correct |
181 ms |
28828 KB |
Output is correct |
4 |
Incorrect |
176 ms |
31808 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |