Submission #396439

#	Time	Username	Problem	Language	Result	Execution time	Memory
396439		12tqian	Food Court (JOI21_foodcourt)	C++17	24 / 100	511 ms	158400 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int N = 5e5 + 5;

 

struct SumSeg {
    vl lz;
    vl st;
    int sz;

    void init(int n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        lz.assign(2 * sz, 0);
        st.assign(2 * sz, 0);
    }

    void pull(int i) {
        st[i] = st[2 * i] + st[2 * i + 1];
    }

    void push(int i, int l, int r) {
        st[i] += (r - l + 1) * lz[i];
        if (l != r) { 
            lz[2 * i] += lz[i];
            lz[2 * i + 1] += lz[i];
        }
        lz[i] = 0;
    }

    void upd(int lo, int hi, ll inc, int i = 1, int l = 0, int r = -1) {
        if (r == -1) r += sz;
        push(i, l, r);
        if (hi < l || r < lo) return;
        if (lo <= l && r <= hi) {
            lz[i] = inc;
            push(i, l, r);
            return;
        }
        int m = (l + r) >> 1;
        upd(lo, hi, inc, 2 * i, l, m);
        upd(lo, hi, inc, 2 * i + 1, m + 1, r);
        pull(i);
    }

    ll query(int lo, int hi, int i = 1, int l = 0, int r = -1) {
        if (r == -1) r += sz;
        push(i, l, r);
        if (hi < l || r < lo) return 0;
        if (lo <= l && r <= hi) return st[i];
        int m = (l + r) >> 1;
        return query(lo, hi, 2 * i, l, m) + query(lo, hi, 2 * i + 1, m + 1, r);
    }
};

template <class C> struct SegmentTreeBeats {
    using T = std::pair<std::pair<C, C>, int>;
    const C INF = std::numeric_limits<C>::max();
    std::vector<C> mx_mod, mn_mod, mod, sum;
    std::vector<T> mx, mn;
    int sz; 

    void init(int sz_) {
        sz = 1; 
        while (sz < sz_) sz *= 2;
        mx_mod.assign(2 * sz, 0);
        mn_mod.assign(2 * sz, 0);
        mod.assign(2 * sz, 0);
        sum.assign(2 * sz, 0);
        mx.assign(2 * sz, {{0, 0}, 0});
        mn.assign(2 * sz, {{0, 0}, 0});
        build();
    }

    void build(int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        mx_mod[ind] = INF, mn_mod[ind] = -INF, mod[ind] = 0;
        if (L == R) {
            mx[ind] = {{0, -INF}, 1};
            mn[ind] = {{0, INF}, 1};
            sum[ind] = 0;
            return;
        }
        int M = (L + R) / 2;
        build(2 * ind, L, M); build(2 * ind + 1, M + 1, R);
        pull(ind);
    }

    T comb_mn(T a, T b) {
        if (a > b) 
            std::swap(a, b);
        if (a.first.first == b.first.first) 
            return  {{a.first.first, 
                std::min(a.first.second, b.first.second)}, 
                a.second + b.second};
        return {{a.first.first, std::min(a.first.second, b.first.first)}, a.second};
    }

    T comb_mx(T a, T b) {
        if (a < b) std::swap(a, b);
        if (a.first.first == b.first.first) 
            return  {{a.first.first, 
                std::max(a.first.second, b.first.second)}, 
                a.second + b.second};
        return {{a.first.first, std::max(a.first.second, b.first.first)}, 
            a.second};
    }

    void pull(int ind) {
        sum[ind] = sum[2 * ind] + sum[2 * ind + 1];
        mn[ind] = comb_mn(mn[2 * ind], mn[2 * ind + 1]);
        mx[ind] = comb_mx(mx[2 * ind], mx[2 * ind + 1]);
    }

    void push(int ind, int L, int R) {
        auto chk = [](C& a, C b, C c) {
            if (a == b)
                a = c;
        };
        if (mn_mod[ind] != -INF) {
            if (mn_mod[ind] > mn[ind].first.first) {
                sum[ind] += (mn_mod[ind] - mn[ind].first.first) * mn[ind].second;
                chk(mx[ind].first.first, mn[ind].first.first, mn_mod[ind]);
                chk(mx[ind].first.second, mn[ind].first.first, mn_mod[ind]);
                mn[ind].first.first = mn_mod[ind];
                if (L != R) {
                    for (int i = 0; i < 2; i++) {
                        int pos = 2 * ind + i;
                        mn_mod[pos] = std::max(mn_mod[pos], mn_mod[ind] - mod[pos]);
                        mx_mod[pos] = std::max(mx_mod[pos], mn_mod[pos]);
                    }
                }
            }
            mn_mod[ind] = -INF;
        }
        if (mx_mod[ind] != INF) {
            if (mx_mod[ind] < mx[ind].first.first) {
                sum[ind] += (mx_mod[ind] - mx[ind].first.first) * mx[ind].second;
                chk(mn[ind].first.first, mx[ind].first.first, mx_mod[ind]);
                chk(mn[ind].first.second, mx[ind].first.first, mx_mod[ind]);
                mx[ind].first.first = mx_mod[ind];
                if (L != R) {
                    for (int i = 0; i < 2; i++) {
                        int pos = 2 * ind + i;
                        mx_mod[pos] = std::min(mx_mod[pos], mx_mod[ind] - mod[pos]);
                        mn_mod[pos] = std::min(mn_mod[pos], mx_mod[pos]);
                    }
                }
            }
            mx_mod[ind] = INF;
        }
        if (mod[ind] != 0) {
            sum[ind] += mod[ind] * (R - L + 1);
            auto inc = [&](T& a, C b) {
                if (std::abs(a.first.first) != INF) 
                    a.first.first += b;
                if (std::abs(a.first.second) != INF)
                    a.first.second += b;
            };
            inc(mx[ind], mod[ind]); inc(mn[ind], mod[ind]);
            if (L != R) {
                for (int i = 0; i < 2; i++) {
                    int pos = 2 * ind + i;
                    mod[pos] += mod[ind];
                }
            }
            mod[ind] = 0;
        }
    }

    C qsum(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (R < lo || hi < L)
            return 0;
        if (lo <= L && R <= hi)     
            return sum[ind];
        int M = (L + R) / 2;
        return qsum(lo, hi, 2 * ind, L, M) + qsum(lo, hi, 2 * ind + 1, M + 1, R);
    }

    C qmax(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (R < lo || hi < L)
            return -INF;
        if (lo <= L && R <= hi)     
            return mx[ind].first.first;
        int M = (L + R) / 2;
        return std::max(qmax(lo, hi, 2 * ind, L, M), qmax(lo, hi, 2 * ind + 1, M + 1, R));
    }

    C qmin(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (R < lo || hi < L)
            return INF;
        if (lo <= L && R <= hi)     
            return mn[ind].first.first;
        int M = (L + R) / 2;
        return std::min(qmin(lo, hi, 2 * ind, L, M), qmin(lo, hi, 2 * ind + 1, M + 1, R));
    }
    
    void upd(int t, int lo, int hi, C b, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (R < lo || hi < L) 
            return;
        if (t == 0) 
            if (b >= mx[ind].first.first)
                return;
        else if (t == 1)
            if (b <= mn[ind].first.first)
                return;
        if (lo <= L && R <= hi) {
            if (t == 0) {
                if (b  > mx[ind].first.second) {
                    mx_mod[ind] = b;
                    push(ind, L, R);
                    return;
                }
            } else if (t == 1) {
                if (b < mn[ind].first.second) {
                    mn_mod[ind] = b;
                    push(ind, L, R);
                    return;
                }
            } else if (t == 2) {
                mod[ind] = b;
                push(ind, L, R);
                return;
            } else assert(false);
        }
        assert(L != R);
        int M = (L + R) / 2;
        upd(t, lo, hi, b, 2 * ind, L, M); upd(t, lo, hi, b, 2 * ind + 1, M + 1, R);
        pull(ind);
    }
};

const ll INF = 1e18;
struct MaxSeg {
    vl lz;
    vector<pair<ll, int>> st;
    int sz;

    void pull(int i) {
        st[i] = max(st[2 * i], st[2 * i + 1]);
    }

    void init(int n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        lz.assign(2 * sz, 0);
        st.resize(2 * sz);
        f0r(i, sz) st[i + sz] = mp(0, i);
        for (int i = sz - 1; i >= 1; i--) pull(i);
    }

    void push(int i, int l, int r) {
        st[i].f += lz[i];
        if (l != r) { 
            lz[2 * i] += lz[i];
            lz[2 * i + 1] += lz[i];
        }
        lz[i] = 0;
    }

    void upd(int lo, int hi, ll inc, int i = 1, int l = 0, int r = -1) {
        if (r == -1) r += sz;
        push(i, l, r);
        if (hi < l || r < lo) return;
        if (lo <= l && r <= hi) {
            lz[i] = inc;
            push(i, l, r);
            return;
        }
        int m = (l + r) >> 1;
        upd(lo, hi, inc, 2 * i, l, m);
        upd(lo, hi, inc, 2 * i + 1, m + 1, r);
        pull(i);
    }

    pair<ll, int> query(int lo, int hi, int i = 1, int l = 0, int r = -1) {
        if (r == -1) r += sz;
        push(i, l, r);
        if (hi < l || r < lo) return mp(-2 * INF, -1);
        if (lo <= l && r <= hi) return st[i];
        int m = (l + r) >> 1;
        return max(query(lo, hi, 2 * i, l, m), query(lo, hi, 2 * i + 1, m + 1, r));
    }
};

vpl queries[N]; 
int ans[N];


int n, m, q;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    vector<array<ll, 5>> que(q);
    SumSeg sseg; sseg.init(n);
    SegmentTreeBeats<ll> seg; seg.init(n);
    f0r(t, q) { 
        int ty; cin >> ty;
        auto& qq = que[t];
        ty--;
        qq[0] = ty;
        if (ty == 0) {
            int l, r, c; ll k; cin >> l >> r >> c >> k;
            l--, r--;
            qq[1] = l;
            qq[2] = r;
            qq[3] = c;
            qq[4] = k;
            sseg.upd(l, r, k);
            seg.upd(2, l, r, k);
        } else if (ty == 1) { 
            int l, r; ll k; cin >> l >> r >> k;
            l--, r--;
            qq[1] = l;
            qq[2] = r;
            qq[3] = k;
            seg.upd(2, l, r, -k);
            seg.upd(1, l, r, 0);
        } else {
            int a, b; cin >> a >> b;
            a--;
            qq[1] = a;
            ll tt = sseg.query(a, a);
            ll c = seg.qsum(a, a);
            ll amt;
            if (b <= c) amt = tt - (c - b);
            else amt = INF;
            qq[2] = amt;
            queries[a].eb(amt, t);
        }
    }
    f0r(i, n) sort(all(queries[i])), reverse(all(queries[i]));
    MaxSeg mseg; mseg.init(n);
    f0r(i, n) {
        if (queries[i].empty()) {
            mseg.upd(i, i, -2 * INF);
            continue;
        }
        mseg.upd(i, i, -queries[i].back().f);
    }
    f0r(t, q) {
        auto& qq = que[t];
        int ty = qq[0];
        if (ty == 0) { 
            int l = qq[1];
            int r = qq[2];
            int c = qq[3];
            int k = qq[4];
            mseg.upd(l, r, k);
            auto res = mseg.query(0, n - 1);
            while (res.f >= 0) {
                int loc = res.s;
                auto done = queries[loc].back();
                ans[done.s] = c;
                mseg.upd(loc, loc, done.f);
                queries[loc].pop_back();
                if (!queries[loc].empty()) {
                    auto nxt = queries[loc].back();
                    mseg.upd(loc, loc, -nxt.f);
                } else {
                    mseg.upd(loc, loc, -INF);
                }
                res = mseg.query(0, n - 1);
            }
        } else if (ty == 1) {
            continue;
        } else {
            continue;
        }
    }
    f0r(i, q) {
        if (que[i][0] != 2) continue;
        cout << ans[i] << '\n';
    }

    return 0;
}

/** 
 * So basically, we can reindex the person, so we want to find the first point in time you have >= x customers at shop i 
 * 
 */

Compilation message (stderr)

foodcourt.cpp: In member function 'void SegmentTreeBeats<C>::upd(int, int, int, C, int, int, int)':
foodcourt.cpp:235:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  235 |         if (t == 0)
      |            ^

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