Submission #1276738

#TimeUsernameProblemLanguageResultExecution timeMemory
1276738duckindogTwo Dishes (JOI19_dishes)C++20
100 / 100
2269 ms342872 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1'000'000 + 10; int n, m; int A[N], S[N], P[N]; int B[N], T[N], Q[N]; map<int, int> p[N]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 0; i < n; ++i) cin >> A[i] >> S[i] >> P[i]; for (int i = 0; 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]; int answer = 0; for (int i = 0; i < n; ++i) { if (S[i] < A[i]) continue; S[i] = upper_bound(B, B + m, S[i] - A[i]) - B; p[i + 1][S[i]] += P[i]; } for (int i = 0; i < m; ++i) { if (T[i] < B[i]) continue; T[i] = upper_bound(A, A + n, T[i] - B[i]) - A; if (T[i] < n) p[T[i] + 1][i] += -Q[i]; answer += Q[i]; } map<int, int> s; for (int i = 1; i <= n; ++i) { p[i][m] += 0; int total = 0; for (auto [r, val] : p[i]) { total += val; s[r + 1] -= val; } s[0] += total; for (auto [r, val] : p[i]) { auto f = s.upper_bound(r); while (f != s.end() && f->first <= m && f->second <= 0) { auto nx = next(f) == end(s) ? m + 1 : next(f)->first; s[nx] += f->second; f = s.erase(f); } } } for (int i = 0; i <= m; ++i) answer += s[i]; cout << answer << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...