Submission #1172154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172154		jakubmz2	Two Dishes (JOI19_dishes)	C++20	0 / 100	268 ms	60884 KiB

dishes

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

const ll MAXN = 1e6 + 5;

ll c1[MAXN];
ll c2[MAXN];
ll t1[MAXN];
ll t2[MAXN];
ll p1[MAXN];
ll p2[MAXN];

ll pref1[MAXN];
ll pref2[MAXN];

ll INF = 1e18;

struct d{
    ll maks = 0;
    ll wdol = 0;
};

ll base = 1 << 20;
d drzew[1 << 21];
ll off = 0;

struct comp{
    bool operator()(const pair<ll,ll> &p1, const pair<ll,ll> &p2) const {
        if(p1.first != p2.first) return p1.first < p2.first;
        if(p1.second != p2.second) return p1.second > p2.second;
        return false;
    }
};

map<pair<ll,ll>, ll, comp> points;

void wdol(ll w){
    ll d = drzew[w].wdol;
    drzew[2 * w].wdol += d;
    drzew[2 * w].maks += d;
    drzew[2 * w + 1].maks += d;
    drzew[2 * w + 1].wdol += d;
    drzew[w].wdol = 0;
    return;
}

ll oblmax(ll w, ll a, ll b, ll akt_a, ll akt_b){
    if(a > b) return -INF;
    //cout << a << " " << akt_a << " " << akt_b << " " << b << " przedz\n";
    if(a <= akt_a and akt_b <= b) {
        return drzew[w].maks;
    }
    if(akt_a > b or akt_b < a) return -INF;
    wdol(w);
    ll mid = (akt_a + akt_b) / 2;
    return max(oblmax(2 * w, a, b, akt_a, mid), oblmax(2 * w + 1, a, b, mid + 1, akt_b));
}

void ustaw(ll w, ll akt_a, ll akt_b, ll ind, ll val){
    if(akt_a == akt_b){
        drzew[w] = {max(drzew[w].maks, val), 0};
        return;
    }
    wdol(w);
    ll mid = (akt_a + akt_b) / 2;
    if(ind <= mid){
        ustaw(2 * w, akt_a, mid, ind, val);
    }
    else{
        ustaw(2 * w + 1, mid + 1, akt_b, ind, val);
    }
    return;
}

void akt(ll w, ll a, ll b, ll akt_a, ll akt_b, ll val){
    if(a > b) return;
    //cout << w << " " << a << " " << b << " " << akt_a << " " << akt_b << " "  << val << " debug\n";
    if(a <= akt_a and akt_b <= b){
        //cout << w << " " << val << " akt\n";
        drzew[w].maks += val;
        drzew[w].wdol += val;
        return;
    }
    if(akt_a > b or akt_b < a) return;
    wdol(w);
    ll mid = (akt_a + akt_b) / 2;
    akt(2 * w, a, b, akt_a, mid, val);
    akt(2 * w + 1, a, b, mid + 1, akt_b, val);
    drzew[w].maks = max(drzew[2 * w].maks, drzew[2 * w + 1].maks);
    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, m;
    cin >> n >> m;
    for(ll i = 1; i < 2 * base; ++i){
        drzew[i] = {0, 0};
    }
    for(ll i = 1; i <= n; ++i){
        cin >> c1[i] >> t1[i] >> p1[i];
        pref1[i] = pref1[i - 1] + c1[i];
    }
    for(ll i = 1; i <= m; ++i){
        cin >> c2[i] >> t2[i] >> p2[i];
        pref2[i] = pref2[i - 1] + c2[i];
    }
    for(ll i = 1; i <= n; ++i){
        if(pref1[i] > t1[i]) continue;
        if(pref1[i] + pref2[m] <= t1[i]){
            //cout << i << " wyj\n";
            off += p1[i];
            continue;
        }
        ll p = 1;
        ll k = m;
        while(p != k){
            ll sr = (p + k + 1) / 2;
            //cout << p << " " << k << " bs1\n";
            if(pref1[i] + pref2[sr] <= t1[i]){
                p = sr;
            }
            else{
                k = sr - 1;
            }
        }
        points[{i - 1, p + 1}] += p1[i];
    }
    for(ll i = 1; i <= m; ++i){
        if(pref2[i] > t2[i]) continue;
        if(pref2[i] + pref1[n] <= t2[i]){
            //cout << i << " wyj2\n";
            off += p2[i];
            continue;
        }
        ll p = 1;
        ll k = n;
        while(p != k){
            //cout << p << " " << k << " bs2\n";
            ll sr = (p + k + 1) / 2;
            if(pref2[i] + pref1[sr] <= t2[i]){
                p = sr;
            }
            else{
                k = sr - 1;
            }
        }
        off += p2[i];
        //cout << i << " " << off << " off\n";
        points[{p, i}] -= p2[i];
    }
    //cout << off << " po\n";
    
    for(auto u : points){
        //cout << off << " pocz\n";
        ll y = u.first.second;
        ll val = u.second;
        //cout << u.first.first << " " << u.first.second << " " << u.second << " point\n";
        ll mx = oblmax(1, 0, y - 1, 0, base - 1);
        //cout << off << " pomax\n";
        //cout << mx << " mx\n";
        //cout << y << " " << mx << " ust\n";
        ustaw(1, 0, base - 1, y, mx);
        //cout << off << " poust\n";
        //cout << 0 << " " << y - 1 << " " << val << " add\n";
        akt(1, 0, y - 1, 0, base - 1, val);
        //cout << off << " poakt\n";
        //cout << drzew[1].maks << " max\n";
        //cout << off << " zmiana\n";
    }
    //cout << off << " off\n";
    cout << drzew[1].maks + off << "\n";

    return 0;
}

• 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