Submission #875916

#TimeUsernameProblemLanguageResultExecution timeMemory
875916vjudge1Two Dishes (JOI19_dishes)C++17
0 / 100
314 ms48100 KiB
// https://oj.uz/problem/view/JOI19_dishes #include <bits/stdc++.h> using namespace std; const int64_t inf = 1e18; class segtree_t { public: segtree_t *left, *right; int l, r, m; int64_t val, lazy_add, lazy_max; segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val(0), lazy_add(0), lazy_max(-inf) { if (l == r) return; left = new segtree_t(l, m); right = new segtree_t(m + 1, r); } void update_add(int s, int t, int64_t x) { if (l > t || r < s) return; if (s <= l && r <= t) { val += x; lazy_add += x; lazy_max += x; return; } Down(); left->update_add(s, t, x); right->update_add(s, t, x); Up(); } void update_max(int s, int t, int64_t x) { if (l > t || r < s) return; if (s <= l && r <= t) { val = max(val, x); lazy_max = max(lazy_max, x); return; } Down(); left->update_max(s, t, x); right->update_max(s, t, x); Up(); } int64_t get(int s, int t) { if (l > t || r < s) return -inf; if (s <= l && r <= t) return val; Down(); return max(left->get(s, t), right->get(s, t)); } void Down() { left->lazy_add += lazy_add; right->lazy_add += lazy_add; left->val += lazy_add; right->val += lazy_add; left->val = max(left->val, lazy_max); right->val = max(right->val, lazy_max); left->lazy_max = max(left->lazy_max, lazy_max); right->lazy_max = max(right->lazy_max, lazy_max); lazy_add = 0; lazy_max = -inf; } void Up() { val = max(left->val, right->val); } }; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<int64_t> a(n + 1), s(n), p(n); vector<int64_t> b(m + 1), t(m), q(m); for (int i = 0; i < n; i++) cin >> a[i + 1] >> s[i] >> p[i]; for (int i = 0; i < m; i++) cin >> b[i + 1] >> t[i] >> q[i]; for (int i = 0; i < n; i++) a[i + 1] += a[i]; for (int i = 0; i < m; i++) b[i + 1] += b[i]; for (int i = 0; i < n; i++) s[i] -= a[i + 1]; for (int i = 0; i < m; i++) t[i] -= b[i + 1]; vector<int> c(n), d(m); for (int i = 0; i < n; i++) c[i] = upper_bound(b.begin(), b.end(), s[i]) - b.begin() - 1; for (int i = 0; i < m; i++) d[i] = upper_bound(a.begin(), a.end(), t[i]) - a.begin() - 1; segtree_t *dp = new segtree_t(0, m); vector<vector<pair<int, int>>> upd(n); for (int i = 0; i < m; i++) { if (d[i] == 0) dp->update_add(i + 1, m, q[i]); if (d[i] > 0) upd[d[i] - 1].emplace_back(i + 1, q[i]); } for (int i = 0; i < n; i++) { sort(upd[i].begin(), upd[i].end()); upd[i].emplace_back(m + 1, -1); if (c[i] != -1) dp->update_add(0, c[i], p[i]); int64_t sum = 0; dp->update_max(c[i] + 1, upd[i][0].first - 1, dp->get(0, c[i])); int last = 0; for (int j = 0; j + 1 < upd[i].size(); j++) { sum += upd[i][j].second; int64_t x = dp->get(last, upd[i][j].first - 1); dp->update_add(upd[i][j].first, upd[i][j + 1].first - 1, sum); dp->update_max(upd[i][j].first, upd[i][j + 1].first - 1, x + upd[i][j].second); last = upd[i][j].first; } } cout << dp->get(m, m); }

Compilation message (stderr)

dishes.cpp: In constructor 'segtree_t::segtree_t(int, int)':
dishes.cpp:14:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |         segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val(0), lazy_add(0), lazy_max(-inf) {
      |                                                 ~~^~~
dishes.cpp: In function 'int32_t main()':
dishes.cpp:103:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |                 for (int j = 0; j + 1 < upd[i].size(); j++) {
      |                                 ~~~~~~^~~~~~~~~~~~~~~
#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...