제출 #579484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579484		Lucpp	Two Dishes (JOI19_dishes)	C++17	65 / 100	972 ms	40536 KiB

dishes

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

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

struct SumSeg{
    vector<ll> S;
    int cap;
    void init(int n){
        for(cap = 1; cap < n; cap*=2);
        S.resize(2*cap);
    }
    void upd(int i, ll v){
        i += cap;
        S[i] = v;
        while(i > 1){
            i /= 2;
            S[i] = S[2*i]+S[2*i+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 0;
        int m = (a+b)/2;
        return 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);}
};
struct MaxSeg{
    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(){
    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);
            // cerr << j << " " << B[i][j] << " " << P[i][j] << "\n";
        }
        // cerr << "\n";
    }
    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());

    SumSeg sumSeg; sumSeg.init(n);
    for(int i = 0; i < n; ++i){
        if(B[0][i] >= 0) sumSeg.upd(i, P[0][i]);
    }
    MaxSeg maxSeg; maxSeg.init(n);
    maxSeg.upd(1, sumSeg.qry(1, n));

    vector<int> todo;
    int lastH = 0;
    for(auto [h, i] : byH){
        if(lastH != h){
            for(int j : todo){
                sumSeg.upd(j, 0);
                maxSeg.add(1, j, -P[0][j]);
            }
            todo.clear();
            for(int j = lastH+1; j <= h; j++){
                if(B[1][j] >= 0){
                    maxSeg.add(1, B[1][j]+1, P[1][j]);
                }
            }
        }
        ll dp = maxSeg.qry(1, i);
        // if(i+1 < n) dp -= sumSeg.qry(i+2, n);
        maxSeg.upd(i+1, dp);
        // cerr << i << " " << h << " " << dp << "\n";
        // cerr << sumSeg.qry(i+2, n) << " " << maxSeg.qry(3, 3) << "\n";
        lastH = h;
        todo.push_back(i);
    }
    ll ans = maxSeg.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: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9