Submission #157257

#	Time	Username	Problem	Language	Result	Execution time	Memory
157257		atoiz	Two Dishes (JOI19_dishes)	C++14	0 / 100	248 ms	48088 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], tree[MAXN];

void build(int root, int lo, int hi)
{

}

void push(int root, int lo, int hi)
{
    if (lo < hi) {
        tree[root << 1] += lazy[root];
        tree[root << 1 | 1] += lazy[root];
        lazy[root << 1] += lazy[root];
        lazy[root << 1 | 1] += lazy[root];
    }
    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));
}

int read()
{
    int 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 (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));
        // FOR(id, 1, M) tree[id] = max(tree[id], tree[id - 1]);
        // FOR(j, 0, M) {
        //     cerr << i << ' ' << j << ": " << get(j) << endl;
        // }
    }

    cout << get(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:115: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:115: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:116: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:116: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: 0 / 5
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9