Submission #804684

#	Time	Username	Problem	Language	Result	Execution time	Memory
804684		TheSahib	Food Court (JOI21_foodcourt)	C++14	100 / 100	838 ms	81288 KiB

foodcourt

#include <bits/stdc++.h>

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

using namespace std;

const int oo = 1e9 + 9;
const pair<ll, ll> dummy = {1e18, 0};
const int MAX = 3e5 + 5;

ll n, m, q;


struct BIT{
    ll T[MAX + 1];
    void update(int pos, int val){
        while(pos < MAX){
            T[pos] += val;
            pos += pos & -pos;
        }
    }
    ll ask(int l, int r){
        if(l != 1) return ask(1, r) - ask(1, l - 1);
        ll ans = 0;
        while(r > 0){
            ans += T[r];
            r -= r & -r;
        }
        return ans;
    }
};

pair<ll, ll> tree[MAX * 5];
ll lazy[MAX * 5];

BIT b1, b2;


void build(int node, int l, int r){
    if(l == r){
        tree[node] = {0, l};
        return;
    }
    int mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}

void relax(int node, int l, int r){
    if(!lazy[node]) return;
    tree[node].first += 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]);
}

pair<ll, ll> ask(int node, int l, int r, int ql, int qr){
    if(ql > r || qr < l) return dummy;
    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][2];
vector<array<ll, 2>> quer[MAX];

int main()
{
    build(1, 0, MAX);
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++)
    {
        int t; scanf("%d", &t);
        if(t == 1){
            int l, r, k; ll c; scanf("%d%d%lld%d", &l, &r, &c, &k);
            events[l][0].push_back({t, i, c, k});
            events[r + 1][1].push_back({t, i, c, k});
        }
        else if(t == 2){
            int l, r, k; scanf("%d%d%d", &l, &r, &k);
            events[l][0].push_back({t, i, 0, k});
            events[r + 1][1].push_back({t, i, 0, k});
        }
        else{
            ll a, b; scanf("%lld%lld", &a, &b);
            quer[a].push_back({i, b});
        }
    }
    vector<ll> ans(q + 1, -1);
    set<pair<int, ll>> st;
    for (int i = 1; i <= n; i++)
    {
        for(auto& e:events[i][0]){
            int idx = e[1], k = e[3]; ll c = e[2];
            if(e[0] == 1){
                update(1, 0, MAX, idx, MAX, k);
                b1.update(idx, k);
                st.insert({idx, c});
            }
            else{
                update(1, 0, MAX, idx, MAX, -k);
                b2.update(idx, k);
            }
        }
        for(auto& e:events[i][1]){
            int idx = e[1], k = e[3]; ll c = e[2];
            if(e[0] == 1){
                update(1, 0, MAX, idx, MAX, -k);
                b1.update(idx, -k);
                st.erase({idx, c});
            }
            else{
                update(1, 0, MAX, idx, MAX, k);
                b2.update(idx, -k);
            }
        }

        for(auto& e:quer[i]){
            int idx = e[0];
            ll b = e[1];
            auto mn = ask(1, 0, MAX, 0, idx);
            mn.second += 1;
            if(mn.second > idx){
                ans[idx] = 0;
                continue;
            }

            ll d = b2.ask(mn.second, idx);
            ll a = -1;
            int l = mn.second, r = idx - 1;
            while(l <= r){
                int mid = (l + r) / 2;
                if(b1.ask(mn.second, mid) - d < b){
                    l = mid + 1;
                }
                else{
                    r = mid - 1;
                    a = mid;
                }
            }
            if(a == -1){
                ans[idx] = 0;
                continue;
            }
            ans[idx] = st.lower_bound({a, 0})->second;
        }
    }
    for (int i = 0; i <= q; i++)
    {
        if(ans[i] < 0) continue;
        cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:94:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         int t; scanf("%d", &t);
      |                ~~~~~^~~~~~~~~~
foodcourt.cpp:96:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |             int l, r, k; ll c; scanf("%d%d%lld%d", &l, &r, &c, &k);
      |                                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:101:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |             int l, r, k; scanf("%d%d%d", &l, &r, &k);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:106:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |             ll a, b; scanf("%lld%lld", &a, &b);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~

• 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