Submission #866620

#	Time	Username	Problem	Language	Result	Execution time	Memory
866620		Dec0Dedd	Food Court (JOI21_foodcourt)	C++14	13 / 100	486 ms	113492 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const ll INF = 1e18;
const int N = 3e5+10;

// value in point queries
// max(a_i+x, b) for (x, b) on [L, R] updates

struct maxtree {
    vector<ll> t;
    vector<pii> lz;

    void init(int k) {
        int sz=1;
        while (sz < 4*k) sz*=2;
        t.resize(sz), lz.resize(sz); 
    }

    void push(int v) {
        lz[2*v] = {
            lz[v].first+lz[2*v].first,
            max(lz[v].first+lz[2*v].second, lz[v].second)
        }, t[2*v]=max(t[2*v]+lz[v].first, lz[v].second);

        lz[2*v+1] = {
            lz[v].first+lz[2*v+1].first,
            max(lz[v].first+lz[2*v+1].second, lz[v].second)
        }, t[2*v+1]=max(t[2*v+1]+lz[v].first, lz[v].second);
        lz[v]={0, 0};
    }

    void upd(int v, int l, int r, int ql, int qr, ll val) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            lz[v].first+=val;
            if (l == r) t[v]=max(t[v]+val, 0ll);
            if (l < r) push(v);
            return;
        } int m=(l+r)/2; push(v);
        upd(2*v, l, m, ql, qr, val), upd(2*v+1, m+1, r, ql, qr, val);
    }

    ll que(int v, int l, int r, int p) {
        if (l == r) return t[v];
        ll m=(l+r)/2; push(v);
        if (p <= m) return que(2*v, l, m, p);
        return que(2*v+1, m+1, r, p);
    }
};

ll tp[N], l[N], r[N], c[N], k[N], lft[N], x[N], ans[N];

struct segtree {
    vector<pii> t;

    void init(int sz) {
        int k=1;
        while (k < 4*sz) k*=2;
        t.resize(k);
    }

    pii mrg(pii l, pii r) {
        return make_pair(l.first+r.first, l.second+r.second);
    }

    void upd(int v, int l, int r, int p, pii val) {
        if (l == r) {
            t[v]=val;
            return;
        } int m=(l+r)/2;
        if (p <= m) upd(2*v, l, m, p, val);
        else upd(2*v+1, m+1, r, p, val);
        t[v]=mrg(t[2*v], t[2*v+1]);
    }

    int que(int v, int l, int r, ll x) {
        if (l == r) return t[v].second;
        int m=(l+r)/2;
        if (t[2*v].first >= x) return que(2*v, l, m, x);
        return que(2*v+1, m+1, r, x-t[2*v].first);
    }
};

vector<int> add[N], rem[N];
vector<int> qx[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m, q; cin>>n>>m>>q;

    maxtree mx, mx2; mx.init(n+10), mx2.init(n+10);
    segtree t; t.init(q+10);

    for (int i=1; i<=q; ++i) {
        cin>>tp[i];
        if (tp[i] == 1) {
            cin>>l[i]>>r[i]>>c[i]>>k[i];
            mx.upd(1, 1, n, l[i], r[i], k[i]);
            mx2.upd(1, 1, n, l[i], r[i], k[i]);
            add[l[i]].push_back(i);
            rem[r[i]+1].push_back(i);
        } else if (tp[i] == 2) {
            cin>>l[i]>>r[i]>>k[i];
            mx.upd(1, 1, n, l[i], r[i], -k[i]);
        } else {
            cin>>l[i]>>r[i];
            lft[i]=mx.que(1, 1, n, l[i]);
            x[i]=r[i]+(mx2.que(1, 1, n, l[i])-lft[i]);
            if (lft[i] < r[i]) ans[i]=-1;
            qx[l[i]].push_back(i);
        }
    }

    for (int i=1; i<=n; ++i) {
        for (auto j : add[i]) t.upd(1, 1, q, j, {k[j], c[j]});
        for (auto j : rem[i]) t.upd(1, 1, q, j, {0, 0});

        for (auto j : qx[i]) {
            if (ans[j] == -1) continue;
            ans[j]=t.que(1, 1, q, x[j]);
        }
    }

    for (int i=1; i<=q; ++i) {
        if (tp[i] != 3) continue;
        if (ans[i] == -1) cout<<0<<"\n";
        else cout<<ans[i]<<"\n";
    }
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 13 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11