Submission #157526

#	Time	Username	Problem	Language	Result	Execution time	Memory
157526		atoiz	Two Dishes (JOI19_dishes)	C++14	100 / 100	6743 ms	191160 KiB

dishes

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cmath>
    #include <climits>
    #include <cassert>
    #include <numeric>
    #include <tuple>
    #include <bitset>
    #include <unordered_map>
    #include <unordered_set>
    #include <map>
    #include <set>
    #include <queue>
    #include <ios>
    #include <iomanip>
    #include <random>
    #include <chrono>
     
    using namespace std;
    using ll = long long;
     
    #define FOR(i, a, b) for (int i = a; i <= b; ++i)
    #define FORA(i, a) for (auto &i : a)
    #define FORB(i, a, b) for (int i = a; i >= b; --i)
    #define SZ(a) ((int) a.size());
    #define ALL(a) begin(a), end(a)
     
    const int MAXN = 1000007;
    const ll INF = 1e16;
    int N, M;
    ll A[MAXN], B[MAXN], S[MAXN], T[MAXN], P[MAXN], Q[MAXN];
    vector<int> ids[MAXN];
    //
    // ll lazy[MAXN << 2], tree[MAXN << 2];
    //
    // void push(int root, int lo, int hi)
    // {
    //     if (lo < hi) {
    //         tree[root << 1] = max(tree[root], tree[root << 1] + lazy[root]);
    //         tree[root << 1 | 1] = max(tree[root], tree[root << 1 | 1] + lazy[root]);
    //         lazy[root << 1] += lazy[root];
    //         lazy[root << 1 | 1] += lazy[root];
    //     } else tree[root] = -INF;
    //     lazy[root] = 0;
    // }
    //
    // void add(int l, int r, ll x, int root = 1, int lo = 0, int hi = M)
    // {
    //     // FOR(i, l, r) tree[i] += x;
    //     // return;
    //     if (r < lo || hi < l) return;
    //     push(root, lo, hi);
    //     if (l <= lo && hi <= r) {
    //         lazy[root] += x;
    //         tree[root] += x;
    //         return;
    //     }
    //
    //     int mid = (lo + hi) >> 1;
    //     add(l, r, x, root << 1, lo, mid);
    //     add(l, r, x, root << 1 | 1, mid + 1, hi);
    // }
    //
    // void upd(int l, int r, ll x, int root = 1, int lo = 0, int hi = M)
    // {
    //     // FOR(i, l, r) tree[i] = max(tree[i], x);
    //     // return;
    //     if (r < lo || hi < l) return;
    //     push(root, lo, hi);
    //     if (l <= lo && hi <= r) {
    //         tree[root] = max(tree[root], x);
    //         return;
    //     }
    //
    //     int mid = (lo + hi) >> 1;
    //     upd(l, r, x, root << 1, lo, mid);
    //     upd(l, r, x, root << 1 | 1, mid + 1, hi);
    // }
    //
    // ll get(int id, int root = 1, int lo = 0, int hi = M)
    // {
    //     // return tree[id];
    //     push(root, lo, hi);
    //     if (lo == hi) return tree[root];
    //
    //     int mid = (lo + hi) >> 1;
    //     if (id <= mid) return max(tree[root], get(id, root << 1, lo, mid));
    //     return max(tree[root], get(id, root << 1 | 1, mid + 1, hi));
    // }
     
    ll cur_max[MAXN << 2], lazy[MAXN << 2], tree[MAXN << 2];
    void push(int root, int lo, int hi)
    {
        if (lo < hi) {
            tree[root << 1] = max(tree[root << 1] + lazy[root], tree[root]);
            tree[root << 1 | 1] = max(tree[root << 1 | 1] + lazy[root], tree[root]);
            cur_max[root << 1] = max(cur_max[root << 1] + lazy[root], tree[root << 1]);
            cur_max[root << 1 | 1] = max(cur_max[root << 1 | 1] + lazy[root], tree[root << 1 | 1]);
            lazy[root << 1] += lazy[root];
            lazy[root << 1 | 1] += lazy[root];
        }
        tree[root] = -INF;
        lazy[root] = 0;
    }
     
    void add(int l, int r, ll x, int root = 1, int lo = 0, int hi = M)
    {
        // if (root == 1) cerr << "Add " << l << ' ' << r << ' ' << x << endl;
        if (r < lo || hi < l) return;
        push(root, lo, hi);
        if (l <= lo && hi <= r) {
            cur_max[root] += x;
            lazy[root] += x;
            tree[root] += x;
            return;
        }
     
        int mid = (lo + hi) >> 1;
        add(l, r, x, root << 1, lo, mid);
        add(l, r, x, root << 1 | 1, mid + 1, hi);
        cur_max[root] = max(tree[root], max(cur_max[root << 1], cur_max[root << 1 | 1]));
    }
     
    void upd(int l, int r, ll x, int root = 1, int lo = 0, int hi = M)
    {
        // if (root == 1) cerr << "Upd " << l << ' ' << r << ' ' << x << endl;
        if (r < lo || hi < l) return;
        push(root, lo, hi);
        if (l <= lo && hi <= r) {
            tree[root] = max(tree[root], x);
            cur_max[root] = max(cur_max[root], x);
            return;
        }
     
        int mid = (lo + hi) >> 1;
        upd(l, r, x, root << 1, lo, mid);
        upd(l, r, x, root << 1 | 1, mid + 1, hi);
        cur_max[root] = max(tree[root], max(cur_max[root << 1], cur_max[root << 1 | 1]));
    }
     
    ll get(int l, int r, int root = 1, int lo = 0, int hi = M)
    {
        ll ans = -INF;
        if (r < lo || hi < l) return ans;
        push(root, lo, hi);
        if (l <= lo && hi <= r) return cur_max[root];
     
        int mid = (lo + hi) >> 1;
        ans = max(ans, get(l, r, root << 1, lo, mid));
        ans = max(ans, get(l, r, root << 1 | 1, mid + 1, hi));
        // if (root == 1) cerr << "Get " << l << ' ' << r << ": " << ans << endl;
        return ans;
    }
     
    ll read()
    {
        ll ans = 0; bool pos = 1; register char ch = getchar();
        for (; ch == ' ' || ch == '\n'; ch = getchar());
        if (ch == '-') pos = 0, ch = getchar();
        for (; 47 < ch && ch < 58; ch = getchar()) ans = ans * 10 + ch - 48;
        return (pos ? ans : -ans);
    }
     
    int main()
    {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        N = read(), M = read();
        FOR(i, 1, N) A[i] = A[i - 1] + read(), S[i] = read(), P[i] = read(); A[N + 1] = INF;
        FOR(i, 1, M) B[i] = B[i - 1] + read(), T[i] = read(), Q[i] = read(); B[M + 1] = INF;
     
        FOR(j, 1, M) ids[upper_bound(A, A + N + 1, T[j] - B[j]) - A].push_back(j);
     
        FOR(i, 1, N + 1) {
            int j = upper_bound(B, B + M + 1, S[i] - A[i]) - B - 1;
            if (j >= 0) add(0, j, P[i]);
     
            vector<int> &vec = ids[i];
            FORA(id, vec) add(id, M, Q[id]);
     
            if (i <= N) {
                if (0 <= j && j < M) vec.insert(lower_bound(vec.begin(), vec.end(), j + 1), j + 1);
                FORA(id, vec) upd(id, M, get(id - 1, id - 1));
            }
            // FOR(id, 1, M) tree[id] = max(tree[id], tree[id - 1]);
            // FOR(j, 0, M) {
            //     cerr << i << ' ' << j << ": " << get(j, j) << endl;
            // }
        }
     
        cout << get(M, M) << endl;
    }

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:28:26: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     #define FOR(i, a, b) for (int i = a; i <= b; ++i)
                          ^
dishes.cpp:174:9: note: in expansion of macro 'FOR'
         FOR(i, 1, N) A[i] = A[i - 1] + read(), S[i] = read(), P[i] = read(); A[N + 1] = INF;
         ^~~
dishes.cpp:174:78: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         FOR(i, 1, N) A[i] = A[i - 1] + read(), S[i] = read(), P[i] = read(); A[N + 1] = INF;
                                                                              ^
dishes.cpp:28:26: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     #define FOR(i, a, b) for (int i = a; i <= b; ++i)
                          ^
dishes.cpp:175:9: note: in expansion of macro 'FOR'
         FOR(i, 1, M) B[i] = B[i - 1] + read(), T[i] = read(), Q[i] = read(); B[M + 1] = INF;
         ^~~
dishes.cpp:175:78: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         FOR(i, 1, M) B[i] = B[i - 1] + read(), T[i] = read(), Q[i] = read(); B[M + 1] = INF;
                                                                              ^

• 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