Submission #875935

#	Time	Username	Problem	Language	Result	Execution time	Memory
875935		vjudge1	Two Dishes (JOI19_dishes)	C++17	100 / 100	6213 ms	322808 KiB

dishes

// 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->lazy_max += lazy_add;
                right->lazy_max += 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]);
                        upd[d[i]].emplace_back(i + 1, 0);
                }
                if (d[i] > 0) {
                        upd[d[i] - 1].emplace_back(i + 1, q[i]);
                        if (d[i] < n) upd[d[i]].emplace_back(i + 1, 0);
                }
        }
        int last = 0;
        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]));
                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);
                        if (c[i] != -1 && upd[i][j].first <= c[i] && c[i] < upd[i][j + 1].first) {
                                int64_t y = dp->get(upd[i][j].first, c[i]);
                                dp->update_max(c[i], upd[i][j + 1].first - 1, y);
                        }
                        last = upd[i][j].first;
                }
        }
        cout << dp->get(last, 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:112: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]
  112 |                 for (int j = 0; j + 1 < upd[i].size(); j++) {
      |                                 ~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9