oj.uz

Submission #875919

# Submission time Handle Problem Language Result Execution time Memory
875919 2023-11-20T18:27:05 Z vjudge1 Two Dishes (JOI19_dishes) C++17
8 / 100
 360 ms 63308 KB 
// 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]);
                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

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:105: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]
  105 |                 for (int j = 0; j + 1 < upd[i].size(); j++) {
      |                                 ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 47956 KB Output is correct
2 Correct 360 ms 61648 KB Output is correct
3 Correct 251 ms 62316 KB Output is correct
4 Correct 264 ms 60624 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 319 ms 60116 KB Output is correct
7 Correct 169 ms 39884 KB Output is correct
8 Correct 66 ms 23848 KB Output is correct
9 Correct 253 ms 63308 KB Output is correct
10 Correct 331 ms 54612 KB Output is correct
11 Correct 227 ms 56772 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 560 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 560 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 4 ms 860 KB Output is correct
20 Incorrect 3 ms 860 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 560 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 4 ms 860 KB Output is correct
20 Incorrect 3 ms 860 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 560 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 4 ms 860 KB Output is correct
20 Incorrect 3 ms 860 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 560 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 4 ms 860 KB Output is correct
20 Incorrect 3 ms 860 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 47956 KB Output is correct
2 Correct 360 ms 61648 KB Output is correct
3 Correct 251 ms 62316 KB Output is correct
4 Correct 264 ms 60624 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 319 ms 60116 KB Output is correct
7 Correct 169 ms 39884 KB Output is correct
8 Correct 66 ms 23848 KB Output is correct
9 Correct 253 ms 63308 KB Output is correct
10 Correct 331 ms 54612 KB Output is correct
11 Correct 227 ms 56772 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 560 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 2 ms 860 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 4 ms 860 KB Output is correct
31 Incorrect 3 ms 860 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 47956 KB Output is correct
2 Correct 360 ms 61648 KB Output is correct
3 Correct 251 ms 62316 KB Output is correct
4 Correct 264 ms 60624 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 319 ms 60116 KB Output is correct
7 Correct 169 ms 39884 KB Output is correct
8 Correct 66 ms 23848 KB Output is correct
9 Correct 253 ms 63308 KB Output is correct
10 Correct 331 ms 54612 KB Output is correct
11 Correct 227 ms 56772 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 560 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 2 ms 860 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 4 ms 860 KB Output is correct
31 Incorrect 3 ms 860 KB Output isn't correct
32 Halted 0 ms 0 KB -