Submission #871547

#TimeUsernameProblemLanguageResultExecution timeMemory
871547qthang2k11Two Dishes (JOI19_dishes)C++17
5 / 100
326 ms165712 KiB
// [+] #include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e6 + 5; int n, m, a[N], b[N], p[N], q[N]; ll s[N], t[N]; ll sum_a[N], sum_b[N]; vector<pair<int, ll>> node[N]; int M; const ll INF = 1e18; struct Node { ll mx, pls, val; Node() { mx = val = -INF; pls = 0; } }; struct LazySegmentTree { Node IT[N << 2]; inline void apply_add(int id, ll w) { IT[id].mx += w; IT[id].val += w; IT[id].pls += w; } inline void apply_max(int id, ll w) { IT[id].mx = max(IT[id].mx, w); IT[id].val = max(IT[id].val, w); } void push(int id) { if (ll &lz = IT[id].pls) { apply_add(id << 1, lz); apply_add(id << 1 | 1, lz); lz = 0; } ll &lz = IT[id].mx; if (lz != -INF) { apply_max(id << 1, lz); apply_max(id << 1 | 1, lz); lz = -INF; } } void update_add(int x, int y, ll w, int id, int l, int r) { if (l > y || r < x) return; if (x <= l && r <= y) return apply_add(id, w); push(id); int mid = (l + r) / 2; update_add(x, y, w, id << 1, l, mid); update_add(x, y, w, id << 1 | 1, mid + 1, r); } inline void update_add(int x, int y, ll w) { // cerr << "update_add(" << x << ", " << y << ", " << w << ")\n"; update_add(x, y, w, 1, 1, M); } void update_max(int x, int y, ll w, int id, int l, int r) { if (l > y || r < x) return; if (x <= l && r <= y) return apply_max(id, w); push(id); int mid = (l + r) / 2; update_max(x, y, w, id << 1, l, mid); update_max(x, y, w, id << 1 | 1, mid + 1, r); } inline void update_max(int x, int y, ll w) { // cerr << "update_max(" << x << ", " << y << ", " << w << ")\n"; update_max(x, y, w, 1, 1, M); } ll get(int x, int id, int l, int r) { if (l == r) return IT[id].val; push(id); int mid = (l + r) / 2; if (x <= mid) return get(x, id << 1, l, mid); else return get(x, id << 1 | 1, mid + 1, r); } inline ll get(int x) { // cerr << "get(" << x << ") = " << get(x, 1, 1, M) << '\n'; return get(x, 1, 1, M); } } seg; // ll debug[1000][1000]; int32_t main() { cin.tie(0)->sync_with_stdio(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++) sum_a[i] = sum_a[i - 1] + a[i]; for (int i = 1; i <= m; i++) sum_b[i] = sum_b[i - 1] + b[i]; for (int i = 1; i <= n; i++) { if (sum_a[i] > s[i]) continue; int pos = ([&] () -> int { int l = 1, r = m, ans = 0; while (l <= r) { int mid = (l + r) / 2; if (sum_a[i] + sum_b[mid] <= s[i]) { ans = mid; l = mid + 1; } else r = mid - 1; } return ans; }()); node[i].emplace_back(pos, p[i]); } ll siu = 0; for (int i = 1; i <= m; i++) { if (sum_b[i] > t[i]) continue; int pos = ([&] () -> int { int l = 1, r = n, ans = 0; while (l <= r) { int mid = (l + r) / 2; if (sum_b[i] + sum_a[mid] <= t[i]) { ans = mid; l = mid + 1; } else r = mid - 1; } return ans; }()); if (pos != n) node[pos + 1].emplace_back(i - 1, -q[i]); siu += q[i]; // cerr << "hihi " << i << ' ' << pos << '\n'; } // cerr << "siu " << siu << '\n'; node[n].emplace_back(m, 0); M = m + 1; seg.update_max(1, M, 0); for (int i = 1; i <= n; i++) { auto &cur = node[i]; sort(cur.begin(), cur.end()); cur.emplace_back(m, 0); vector<pair<int, ll>> tmp; for (const auto &elem: cur) { if (tmp.empty() || tmp.back().first != elem.first) tmp.emplace_back(elem); else tmp.back().second += elem.second; } // for (auto [j, val]: tmp) // debug[i][j] = val, // cerr << string(10, ' ') << "[" << i << ", " << j << "] = " << val << '\n'; ll sum = 0; for (auto &elem: tmp) { elem.first++; sum += elem.second; } // cerr << "i = " << i << ", sum = " << sum << '\n'; ll pre_max = -INF; for (int i = 0; i < (int)tmp.size(); i++) { int L = 1, R = tmp[i].first; if (i - 1 >= 0) L = tmp[i - 1].first + 1; // cerr << L << ' ' << R << '\n'; seg.update_add(L, R, sum); pre_max = max(pre_max, seg.get(R)); seg.update_max(L, R, pre_max); sum -= tmp[i].second; } // ll pre_max = LLONG_MIN; // for (const auto &elem: tmp) { // int pos = upper_bound(arr.begin(), arr.end(), elem.first) - arr.begin(); // // dp[pos] = max(dp[pos] + sum, pre_max); // // pre_max = max(pre_max, dp[pos]); // sum -= elem.second; // } // cerr << "at i = " << i << '\n'; // for (const auto &elem: tmp) // cerr << elem.first << ' ' << elem.second << '\n'; // // for (int j = 1; j <= M; j++) // fprintf(stderr, "dp[%d][%d] = %lld\n", i, j - 1, seg.get(j)); // cerr << '\n'; } // cerr << "siu = " << siu << '\n'; cout << seg.get(M) + siu; // for (int i = m; i >= 0; i--) // for (int j = 1; j <= n; j++) // cerr << debug[j][i] << " \n"[j == n]; return 0; }
#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...