Submission #348889

#	Time	Username	Problem	Language	Result	Execution time	Memory
348889		ijxjdjd	Two Dishes (JOI19_dishes)	C++14	100 / 100	5409 ms	263264 KiB

dishes

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;
const int MAXN = (int)(1e6)+5;
ll A[MAXN];
ll S[MAXN];
ll B[MAXN];
ll T[MAXN];
ll P[MAXN];
ll Q[MAXN];
ll prefA[MAXN];
ll prefB[MAXN];
ll lzy[4*MAXN];
ll mx[4*MAXN];
void push(int n) {
    lzy[2*n] += lzy[n];
    lzy[2*n+1] += lzy[n];
    mx[2*n] += lzy[n];
    mx[2*n+1] += lzy[n];
    lzy[n] = 0;
}
void add(int n, int tl, int tr, int l, int r, ll ad) {
    if (tr < l || r < tl) {
        return;
    }
    if (l <= tl && tr <= r) {
        lzy[n] += ad;
        mx[n] += ad;
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        add(2*n, tl, tm, l, r, ad);
        add(2*n+1, tm+1, tr, l, r, ad);
        mx[n] = max(mx[2*n], mx[2*n+1]);
    }
}
ll query(int n, int tl, int tr, int l, int r) {
   if (tr < l || r < tl) {
        return ll(-1e18);
    }
    if (l <= tl && tr <= r) {
        return mx[n];
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        return max(query(2*n, tl, tm, l, r), query(2*n+1, tm+1, tr, l, r));
    }
}
void upd(int n, int tl, int tr, int i, ll val) {
    if (tl == tr) {
        mx[n] = max(mx[n], val);
        lzy[n] = 0;
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        if (i <= tm) {
            upd(2*n, tl, tm, i, val);
        }
        else {
            upd(2*n+1, tm+1, tr, i, val);
        }
        mx[n] = max(mx[2*n], mx[2*n+1]);
    }
}
vector<pair<int, ll>> row[MAXN];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, M;
	cin >> N >> M;
	FR(i, 4*MAXN) {
        mx[i] = (ll)(-1e18);
	}
	for (int i = 1; i <= N; i++) {
        cin >> A[i] >> S[i] >> P[i];
        prefA[i] = A[i] + prefA[i-1];
	}
	for (int i = 1; i <= M; i++) {
        cin >> B[i] >> T[i] >> Q[i];
        prefB[i] = B[i] + prefB[i-1];
	}
	ll offset = 0;
	for (int i = 1; i <= N; i++) {
        if (prefA[i] <= S[i]) {
            int low = 0;
            int high = M;
            ll g = S[i] - prefA[i];
            while (low < high) {
                int mid = (low + high+1)/2;
                if (prefB[mid] <= g) {
                    low = mid;
                }
                else {
                    high = mid-1;
                }
            }
            row[i].push_back({low, P[i]});
        }
	}
	for (int i = 1; i <= M; i++) {
        if (prefB[i] <= T[i]) {
            int low = 0;
            int high = N;
            ll g = T[i] - prefB[i];
            while (low < high) {
                int mid = (low + high+1)/2;
                if (prefA[mid] <= g) {
                    low = mid;
                }
                else {
                    high = mid-1;
                }
            }
            offset += Q[i];
            if (low != N) {
                row[low+1].push_back({i-1, -Q[i]});
            }
        }
	}
	upd(1, 0, M, 0, 0);
	FR(i, N+1) {
        sort(row[i].begin(), row[i].end());
        while (row[i].size()) {
            while (row[i].size() != 1) {
                if (row[i][row[i].size()-1].first == row[i][row[i].size()-2].first) {
                    row[i][row[i].size()-2].second += row[i][row[i].size()-1].second;
                    row[i].pop_back();
                }
                else {
                    break;
                }
            }
            upd(1, 0, M, row[i].back().first+1, query(1, 0, M, 0, row[i].back().first));
            add(1, 0, M, 0, row[i].back().first, row[i].back().second);
            row[i].pop_back();
        }
	}
	cout << mx[1] + offset;
	return 0;
}

• 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