Submission #804447

#	Time	Username	Problem	Language	Result	Execution time	Memory
804447		TheSahib	Food Court (JOI21_foodcourt)	C++14	13 / 100	1080 ms	57540 KiB

foodcourt

#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>

using namespace std;

const int oo = 1e9 + 9;
const int MAX = 3e5 + 5;

ll n, m, q;



ll tree[MAX * 5];
ll lazy[MAX * 5];

void relax(int node, int l, int r){
    if(!lazy[node]) return;
    tree[node] += lazy[node];
    if(l != r){
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void update(int node, int l, int r, int ql, int qr, int val){
    relax(node, l, r);
    if(ql > r || qr < l) return;
    if(ql <= l && r <= qr){
        lazy[node] += val;
        relax(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(node * 2, l, mid, ql, qr, val);
    update(node * 2 + 1, mid + 1, r, ql, qr, val);
    tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}

ll ask(int node, int l, int r, int ql, int qr){
    if(ql > r || qr < l) return 1e18;
    relax(node, l, r);
    if(ql <= l && r <= qr){
        return tree[node];
    }
    int mid = (l + r) / 2;
    return min(ask(node * 2, l, mid, ql, qr), ask(node * 2 + 1, mid + 1, r, ql, qr));
}

vector<array<ll, 4>> events[MAX];
vector<array<ll, 2>> quer[MAX];

int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++)
    {
        int t; cin >> t;
        if(t == 1){
            ll l, r, c, k; cin >> l >> r >> c >> k;
            events[l].push_back({t, i, c, k});
            events[r + 1].push_back({-t, i, c, k});
        }
        else if(t == 2){
            ll l, r, k; cin >> l >> r >> k;
            events[l].push_back({t, i, 0, -k});
            events[r + 1].push_back({-t, i, 0, -k});
        }
        else{
            ll a, b; cin >> a >> b;
            quer[a].push_back({i, b});
        }
    }
    vector<int> ans(q + 1, -1);
    set<pii> st;
    for (int i = 1; i <= n; i++)
    {
        for(auto& e:events[i]){
            if(e[0] > 0){
                update(1, 0, MAX, e[1], MAX, e[3]);
                if(e[0] == 1){
                    st.insert({e[1], e[2]});
                }
            }
            else{
                update(1, 0, MAX, e[1], MAX, -e[3]);
                if(e[0] == -1){
                    st.erase({e[1], e[2]});
                }
            }
        }
        for(auto& e:quer[i]){
            int idx = e[0];
            ll b = e[1];
            ll mn = ask(1, 0, MAX, 0, idx);
            ll a = ask(1, 0, MAX, idx, idx);
            if(a - mn < b){
                ans[idx] = 0;
                continue;
            }
            int l = 0, r = idx - 1;
            int c = 0;
            while(l <= r){
                int mid = (l + r) / 2;
                if(ask(1, 0, MAX, mid, idx) - mn < b){
                    l = mid + 1;
                    c = mid;
                }
                else{
                    r = mid - 1;
                }
            }
            auto itr = st.upper_bound({c, oo});
            ans[idx] = itr->second;
        }
    }
    for (int i = 0; i <= q; i++)
    {
        if(ans[i] < 0) continue;
        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