Submission #157268

#	Time	Username	Problem	Language	Result	Execution time	Memory
157268		atoiz	Two Dishes (JOI19_dishes)	C++14	100 / 100	7024 ms	227088 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(0, 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:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(i, a, b) for (int i = a; i <= b; ++i)
                      ^
dishes.cpp:174:5: 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:74: 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:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(i, a, b) for (int i = a; i <= b; ++i)
                      ^
dishes.cpp:175:5: 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:74: 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