#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
const int MAXN = 200005;
const llint INF = 1000000000000000000LL;
llint n, m, sol;
llint a[MAXN], b[MAXN], s[MAXN], t[MAXN], p[MAXN], q[MAXN];
llint suma[MAXN], sumb[MAXN], d[MAXN], lim[MAXN];
vector <int> v[MAXN];
set <int> st;
void upd (int pos) {
st.insert(pos);
llint ofs = 0;
while (pos <= m) {
int nxt = *st.upper_bound(pos);
if (d[pos] - ofs > lim[pos]) {
d[pos] -= ofs;
break;
}
ofs += lim[pos] - d[pos];
d[pos] = lim[pos];
st.erase(pos);
pos = nxt;
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> s[i] >> p[i];
suma[i] = suma[i - 1] + a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i] >> t[i] >> q[i];
sumb[i] = sumb[i - 1] + b[i];
if (sumb[i] > t[i]) continue;
d[i] = lim[i] = q[i];
int ind = upper_bound(suma, suma + n + 1, t[i] - sumb[i]) - suma - 1;
v[ind].push_back(i);
}
st.insert(m + 1);
for (int i = 1; i <= n; i++) {
if (suma[i] <= s[i]) {
int ind = upper_bound(sumb, sumb + m + 1, s[i] - suma[i]) - sumb - 1;
d[0] += p[i];
d[ind + 1] -= p[i];
upd(ind + 1);
}
for (auto x : v[i]) {
lim[x] = 0;
upd(x);
}
}
for (int i = 0; i <= m; i++) sol += d[i];
cout << sol;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
315 ms |
46076 KB |
Output is correct |
2 |
Correct |
298 ms |
39288 KB |
Output is correct |
3 |
Correct |
319 ms |
44304 KB |
Output is correct |
4 |
Incorrect |
318 ms |
42516 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
5120 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
5120 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
5120 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
5120 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
5120 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
315 ms |
46076 KB |
Output is correct |
2 |
Correct |
298 ms |
39288 KB |
Output is correct |
3 |
Correct |
319 ms |
44304 KB |
Output is correct |
4 |
Incorrect |
318 ms |
42516 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
315 ms |
46076 KB |
Output is correct |
2 |
Correct |
298 ms |
39288 KB |
Output is correct |
3 |
Correct |
319 ms |
44304 KB |
Output is correct |
4 |
Incorrect |
318 ms |
42516 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |