Submission #165850

#	Time	Username	Problem	Language	Result	Execution time	Memory
165850		choikiwon	Two Dishes (JOI19_dishes)	C++17	100 / 100	6018 ms	459972 KiB

dishes

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2000010;

int N, M;
ll A[maxn], B[maxn], S[maxn], T[maxn], P[maxn], Q[maxn], nA[maxn], nB[maxn], nS[maxn], nT[maxn], nP[maxn], nQ[maxn];
int X[maxn], Y[maxn], inv[maxn], pnt[maxn];
pii ord[maxn];

vector<int> adj1[maxn], adj2[maxn];
ll dp[maxn];
ll offset;

struct BIT {
    ll tree[4 * maxn];
    ll lazy[4 * maxn];
    void init() {
        for(int i = 0; i < 4 * N; i++) {
            tree[i] = -1e17;
            lazy[i] = 0;
        }
    }
    void prop(int l, int r, int n) {
        if(l != r) {
            tree[2*n] += lazy[n];
            lazy[2*n] += lazy[n];
            tree[2*n + 1] += lazy[n];
            lazy[2*n + 1] += lazy[n];
            lazy[n] = 0;
        }
    }
    void upd(int a, int b, ll d, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            tree[n] += d;
            lazy[n] += d;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd(a, b, d, l, m, 2*n);
        upd(a, b, d, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    void upd2(int x, ll v, int l, int r, int n) {
        if(x < l || r < x) return;
        if(l == r) {
            tree[n] = v;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd2(x, v, l, m, 2*n);
        upd2(x, v, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    ll quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return -1e18;
        if(a <= l && r <= b) return tree[n];
        prop(l, r, n);
        int m = (l + r)>>1;
        ll L = quer(a, b, l, m, 2*n);
        ll R = quer(a, b, m + 1, r, 2*n + 1);
        return max(L, R);
    }
} bit;

void proc() {
    for(int i = 0; i < N; i++) {
        if(A[i] > S[i]) P[i] = 0;
        X[i] = upper_bound(B, B + M, S[i] - A[i]) - B;
    }
    for(int i = 0; i < M; i++) {
        if(B[i] > T[i]) Q[i] = 0;
        Y[i] = upper_bound(A, A + N, T[i] - B[i]) - A;
    }

    for(int i = 0; i < M; i++) adj1[i].clear();
    for(int i = 0; i < N; i++) adj2[i].clear();
    for(int i = 0; i < N; i++) adj1[ X[i] ].push_back(i);
    for(int i = 0; i < M; i++) adj2[ Y[i] ].push_back(i);
}

ll getInt() {
    ll ret = 0;
    bool s = false;
    while(1) {
        char c = getchar();
        if(c == ' ' || c == '\n') break;
        if(c == '-') {
            s = true;
            continue;
        }

        ret = (ret << 3) + (ret << 1);
        ret += c - '0';
    }
    return s? -ret : ret;
}

int main() {
    N = getInt();
    M = getInt();

    for(int i = 0; i < N; i++) {
        A[i] = getInt();
        S[i] = getInt();
        P[i] = getInt();
    }
    for(int i = 0; i < M; i++) {
        B[i] = getInt();
        T[i] = getInt();
        Q[i] = getInt();
    }

    for(int i = 1; i < N; i++) A[i] += A[i - 1];
    for(int i = 1; i < M; i++) B[i] += B[i - 1];

    proc();

    for(int i = 0; i < N; i++) if(P[i] < 0) offset += P[i];
    for(int i = 0; i < M; i++) if(Q[i] < 0) offset += Q[i];

    int cnt1 = 0;
    int cnt2 = 0;

    for(int i = 0; i < N; i++) {
        if(P[i] >= 0) {
            nA[cnt1] = A[i];
            nS[cnt1] = S[i];
            nP[cnt1] = P[i];
            cnt1++;
        }
        /*
        else {
            nA[cnt1] = A[i];
            nS[cnt1] = S[i];
            nP[cnt1] = 0;
            cnt1++;
        }
        //*/

        for(int j = 0; j < adj2[i].size(); j++) {
            int k = adj2[i][j];

            if(Q[k] < 0) {
                nA[cnt1] = A[i];
                nS[cnt1] = A[i] + B[k] - 1;
                nP[cnt1] = -Q[k];
                cnt1++;
            }
        }
    }
    for(int i = 0; i < M; i++) {
        if(Q[i] >= 0) {
            nB[cnt2] = B[i];
            nT[cnt2] = T[i];
            nQ[cnt2] = Q[i];
            cnt2++;
        }
        /*
        else {
            nB[cnt2] = B[i];
            nT[cnt2] = T[i];
            nQ[cnt2] = 0;
            cnt2++;
        }
        //*/

        for(int j = 0; j < adj1[i].size(); j++) {
            int k = adj1[i][j];

            if(P[k] < 0) {
                nB[cnt2] = B[i];
                nT[cnt2] = B[i] + A[k] - 1;
                nQ[cnt2] = -P[k];
                cnt2++;
            }
        }
    }

    N = cnt1;
    M = cnt2;
    for(int i = 0; i < N; i++) {
        A[i] = nA[i];
        S[i] = nS[i];
        P[i] = nP[i];
    }
    for(int i = 0; i < M; i++) {
        B[i] = nB[i];
        T[i] = nT[i];
        Q[i] = nQ[i];
    }

    proc();

    //*/

    for(int i = 0; i < N; i++) ord[i] = pii(X[i], -i);
    sort(ord, ord + N);
    for(int i = 0; i < N; i++) inv[ -ord[i].second ] = i;
    int pos = 0;
    for(int i = 0; i < M; i++) {
        while(pos < N && ord[pos].first <= i) pos++;
        pnt[i] = pos - 1;
    }

    for(int i = 0; i < M; i++) offset += Q[i];

    bit.init();
    for(int i = N - 1; i >= 0; i--) {
        dp[i] = bit.quer(inv[i] + 1, N - 1, 0, N - 1, 1);
        dp[i] = max(0LL, dp[i]);

        bit.upd2(inv[i], dp[i], 0, N - 1, 1);
        bit.upd(0, inv[i], P[i], 0, N - 1, 1);

        for(int j = 0; j < adj2[i].size(); j++) {
            int k = adj2[i][j];

            bit.upd(0, pnt[k], -Q[k], 0, N - 1, 1);
        }
    }

    ll ans = bit.tree[1];
    ans = max(0LL, ans);

    printf("%lld", ans + offset);
}

Compilation message (stderr)

dishes.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
dishes.cpp: In function 'int main()':
dishes.cpp:151:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < adj2[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~
dishes.cpp:178:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < adj1[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~
dishes.cpp:226:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < adj2[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