Submission #579488

#	Time	Username	Problem	Language	Result	Execution time	Memory
579488		Lucpp	Two Dishes (JOI19_dishes)	C++17	74 / 100	3082 ms	96236 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAX = 1e6+2;

ll A[2][MAX], T[2][MAX], P[2][MAX];
int B[2][MAX];

struct Seg{
    vector<ll> S, O;
    vector<bool> lazy;
    int cap;
    void init(int n){
        for(cap = 1; cap < n; cap*=2);
        S.assign(2*cap, -INF);
        O.assign(2*cap, 0);
        lazy.assign(2*cap, false);
    }
    void push(int i){
        if(lazy[i]){
            S[2*i] += O[i];
            O[2*i] += O[i];
            lazy[2*i] = true;
            S[2*i+1] += O[i];
            O[2*i+1] += O[i];
            lazy[2*i+1] = true;
            O[i] = 0;
            lazy[i] = false;
        }
    }
    void add(int l, int r, ll v, int a, int b, int i){
        if(l <= a && b <= r){
            S[i] += v;
            O[i] += v;
            lazy[i] = true;
        }
        else if(b < l || r < a);
        else{
            push(i);
            int m = (a+b)/2;
            add(l, r, v, a, m, 2*i);
            add(l, r, v, m+1, b, 2*i+1);
            S[i] = max(S[2*i], S[2*i+1]);
        }
    }
    void add(int l, int r, ll v){add(l, r, v, 1, cap, 1);}
    void upd(int p, ll v, int a, int b, int i){
        if(a == b) S[i] = v;
        else{
            push(i);
            int m = (a+b)/2;
            if(p <= m) upd(p, v, a, m, 2*i);
            else upd(p, v, m+1, b, 2*i+1);
            S[i] = max(S[2*i], S[2*i+1]);
        }
    }
    void upd(int p, ll v){upd(p, v, 1, cap, 1);}
    ll qry(int l, int r, int a, int b, int i){
        if(l <= a && b <= r) return S[i];
        if(b < l || r < a) return -INF;
        push(i);
        int m = (a+b)/2;
        return max(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
    }
    ll qry(int l, int r){return qry(l, r, 1, cap, 1);}
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < 2; i++){
        A[i][0] = P[i][0] = 0;
        for(int j = 1; j <= (i==0?n:m); j++){
            cin >> A[i][j] >> T[i][j] >> P[i][j];
            A[i][j] += A[i][j-1];
        }
    }
    
    for(int i = 0; i < 2; i++){
        B[i][0] = 0;
        int x = (i==0?m:n);
        for(int j = 1; j <= (i==0?n:m); j++){
            if(A[i][j] > T[i][j]) B[i][j] = -1;
            else if(A[i][j]+A[1-i][x] <= T[i][j]) B[i][j] = x;
            else B[i][j] = (int)(upper_bound(A[1-i], A[1-i]+x, T[i][j]-A[i][j])-A[1-i]-1);
        }
    }
    n++;
    B[0][n] = m;
    P[0][n] = 0;
    n++;

    vector<pair<int, int>> byH;
    for(int i = 1; i < n; i++) if(B[0][i] >= 0) byH.emplace_back(B[0][i], i);
    sort(byH.begin(), byH.end());

    ll sum = 0;
    for(int i = 0; i < n; ++i){
        if(B[0][i] >= 0) sum += P[0][i];
    }
    Seg seg; seg.init(n);
    seg.upd(1, sum);

    vector<int> todo;
    int lastH = 0;
    for(auto [h, i] : byH){
        if(lastH != h){
            for(int j : todo){
                seg.add(1, j, -P[0][j]);
            }
            todo.clear();
            for(int j = lastH+1; j <= h; j++){
                if(B[1][j] >= 0){
                    seg.add(1, B[1][j]+1, P[1][j]);
                }
            }
        }
        ll dp = seg.qry(1, i);
        seg.upd(i+1, dp);
        lastH = h;
        todo.push_back(i);
    }
    ll ans = seg.qry(n, n);
    cout << ans << "\n";
}

• 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: 0 / 17
• Subtask 8: 0 / 9