Submission #165829

#	Time	Username	Problem	Language	Result	Execution time	Memory
165829		choikiwon	Two Dishes (JOI19_dishes)	C++17	0 / 100	100 ms	94200 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];
int X[maxn], Y[maxn], inv[maxn], pnt[maxn];

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

struct BIT {
    vector<ll> tree, lazy;
    void init() {
        tree = vector<ll>(4 * N, -1e17);
        lazy = vector<ll>(4 * N, 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;

        int s = 0, e = M - 1, p = M;
        while(s <= e) {
            int m = (s + e)>>1;

            if(A[i] + B[m] > S[i]) {
                p = m;
                e = m - 1;
            }
            else s = m + 1;
        }
        X[i] = p;
    }
    for(int i = 0; i < M; i++) {
        if(B[i] > T[i]) Q[i] = 0;

        int s = 0, e = N - 1, p = N;
        while(s <= e) {
            int m = (s + e)>>1;

            if(B[i] + A[m] > T[i]) {
                p = m;
                e = m - 1;
            }
            else s = m + 1;
        }
        Y[i] = p;
    }

    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);
}

int main() {
    freopen("in.txt", "r", stdin);

    scanf("%d %d", &N, &M);

    for(int i = 0; i < N; i++) {
        scanf("%lld %lld %lld", &A[i], &S[i], &P[i]);
    }
    for(int i = 0; i < M; i++) {
        scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
    }

    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];

    //*
    vector<ll> nA, nB, nS, nT, nP, nQ;
    for(int i = 0; i < N; i++) {
        if(P[i] >= 0) {
            nA.push_back(A[i]);
            nS.push_back(S[i]);
            nP.push_back(P[i]);
        }
        else {
            nA.push_back(A[i]);
            nS.push_back(S[i]);
            nP.push_back(0);
        }

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

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

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

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

    N = nA.size();
    M = nB.size();
    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();

    //*/

    vector<pii> ord;
    for(int i = 0; i < N; i++) ord.push_back(pii(X[i], -i));
    sort(ord.begin(), ord.end());
    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]);

        //cout << dp[i] << endl;

        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.quer(0, N - 1, 0, N - 1, 1);
    ans = max(0LL, ans);

    cout << 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:144:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < adj2[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~
dishes.cpp:166:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < adj1[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~
dishes.cpp:217:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < adj2[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~
dishes.cpp:111:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("in.txt", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
dishes.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &A[i], &S[i], &P[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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