Submission #998657

#	Time	Username	Problem	Language	Result	Execution time	Memory
998657		vladilius	Food Court (JOI21_foodcourt)	C++17	100 / 100	421 ms	53584 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define pb push_back
#define ff first
#define ss second
#define ins insert

struct ST{
    struct node{
        ll sum, max_suf;
    };
    using pni = pair<node, int>;
    vector<node> t;
    node null;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
        null = {0, 0};
    }
    node merge(node x, node y){
        return {x.sum + y.sum, max(y.max_suf, x.max_suf + y.sum)};
    }
    void upd(int v, int tl, int tr, int& p, int& k){
        if (tl == tr){
            t[v] = {k, k};
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, k);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, k);
        }
        t[v] = merge(t[vv], t[vv + 1]);
    }
    void upd(int p, int k){
        upd(1, 1, n, p, k);
    }
    node get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return null;
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2, vv = 2 * v;
        return merge(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
    }
    ll get(int l, int r){
        return get(1, 1, n, l, r).max_suf;
    }
};
 
struct ST1{
    vector<ll> t;
    int n;
    ST1(int ns){
        n = ns;
        t.resize(4 * n);
    }
    void upd(int v, int tl, int tr, int& p, int& k){
        if (tl == tr){
            t[v] = k;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, k);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, k);
        }
        t[v] = t[vv] + t[vv + 1];
    }
    void upd(int p, int k){
        upd(1, 1, n, p, k);
    }
    ll get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2, vv = 2 * v;
        return get(vv, tl, tm, l, r) + get(vv + 1, tm + 1, tr, l, r);
    }
    ll get(int l, int r){
        return get(1, 1, n, l, r);
    }
    int get_p(int r, ll k){
        int bl = 1, br = r;
        while (bl + 1 < br){
            int m = (bl + br) / 2;
            if (get(1, m) >= k){
                br = m;
            }
            else {
                bl = m + 1;
            }
        }
        if (get(1, bl) >= k) br = bl;
        return br;
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, q; cin>>n>>m>>q;
    vector<pii> st[n + 2];
    vector<pil> qs[n + 1];
    vector<int> col(q + 1);
    for (int tt = 1; tt <= q; tt++){
        int type; cin>>type;
        if (type == 1){
            int l, r, c, k; cin>>l>>r>>c>>k;
            st[l].pb({tt, k});
            st[r + 1].pb({tt, 0});
            col[tt] = c;
        }
        else if (type == 2){
            int l, r, k; cin>>l>>r>>k;
            st[l].pb({tt, -k});
            st[r + 1].pb({tt, 0});
        }
        else {
            int a; ll b; cin>>a>>b;
            qs[a].pb({tt, b});
        }
    }
    ST T(q);
    ST1 Ts(q);
    vector<int> out(q + 1, -1);
    for (int i = 1; i <= n; i++){
        for (auto [j, k]: st[i]){
            T.upd(j, k);
            if (k >= 0) Ts.upd(j, k);
        }
        for (auto [j, b]: qs[i]){
            ll cur = T.get(1, j);
            if (b > cur){
                out[j] = 0;
                continue;
            }
            b = Ts.get(1, j) - cur + b;
            out[j] = col[Ts.get_p(j, b)];
        }
    }
    for (int i = 1; i <= q; i++){
        if (out[i] != -1){
            cout<<out[i]<<"\n";
        }
    }
}

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