Submission #495472

#	Time	Username	Problem	Language	Result	Execution time	Memory
495472		danikoynov	Food Court (JOI21_foodcourt)	C++14	100 / 100	822 ms	82872 KiB

foodcourt

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;
const ll maxn = 250010;
const ll inf = 1e17;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


struct segment_tree_modified
{

    pair < ll, ll > lazy[4 * maxn];
    ll tree[4 * maxn];

    pair < ll, ll > merge_lazy(pair < ll, ll > p1, pair < ll, ll > p2)
    {
        if (p1.second > p2.first)
        {
            return {p1.first, p1.second - p2.first + p2.second};
        }
        else
        {
            return {p1.first - p1.second + p2.first, p2.second};
        }
    }
    void push_lazy(ll root, ll left, ll right)
    {
        if (left == right)
        {
            tree[root] = max((ll)(0), tree[root] - lazy[root].first) + lazy[root].second;

        }
        else
        {
            lazy[root * 2] = merge_lazy(lazy[root * 2], lazy[root]);
            lazy[root * 2 + 1] = merge_lazy(lazy[root * 2 + 1], lazy[root]);
        }
        lazy[root] = {0, 0};
    }

    void range_update(ll root, ll left, ll right, ll qleft, ll qright,
                      pair < ll, ll > val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
            return;
        if (left >= qleft && right <= qright)
        {
            lazy[root] = val;
            push_lazy(root, left, right);
            return;
        }

        ll mid = (left + right) / 2;
        range_update(root * 2, left, mid, qleft, qright, val);
        range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);
    }

    ll query(ll root, ll left, ll right, ll idx)
    {
        ///cout << left << " - " << right << " " << lazy[root].first << " " << lazy[root].second << endl;
        push_lazy(root, left, right);
        if (left == right)
            return tree[root];

        ll mid = (left + right) /2;
        if (idx <= mid)
            return query(root * 2, left, mid, idx);
        return query(root * 2 + 1, mid + 1, right, idx);
    }

};

struct node
{
    ll minx, min_idx;

    node()
    {
        minx = inf;
    }
};

node merge_nodes(node nd1, node nd2)
{
    if (nd1.minx < nd2.minx)
        return nd1;
    return nd2;
}

struct segment_tree
{



    ll lazy[4 * maxn];
    node tree[4 * maxn];

    void push_lazy(ll root, ll left, ll right)
    {
        tree[root].minx += lazy[root];
        if (left == right)
            tree[root].min_idx = left;

        if (left != right)
        {
            lazy[root * 2] += lazy[root];
            lazy[root * 2 + 1] += lazy[root];
        }

        lazy[root] = 0;
    }

    void range_update(ll root, ll left, ll right,
                      ll qleft, ll qright, ll val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            lazy[root] += val;
            push_lazy(root, left, right);
            return;
        }

        ll mid = (left + right) / 2;
        range_update(root * 2, left, mid, qleft, qright, val);
        range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);

        tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
    }


    void poll_update(ll root, ll left, ll right, ll idx, ll val)
    {
        push_lazy(root, left, right);
        if (left == right)
        {
            tree[root].minx = val;
            tree[root].min_idx = left;
            return;
        }

        ll mid = (left + right) / 2;
        if (idx <= mid)
            poll_update(root * 2, left, mid, idx, val);
        else
            poll_update(root * 2 + 1, mid + 1, right, idx, val);
        push_lazy(root * 2, left, mid);
        push_lazy(root * 2 + 1, mid + 1, right);
        tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
    }

    node query(ll root, ll left, ll right, ll idx)
    {
        push_lazy(root, left, right);
        if (left == right)
            return tree[root];

        ll mid = (left + right) / 2;
        if (idx <= mid)
            return query(root * 2, left, mid, idx);
        return query(root * 2 + 1, mid + 1, right, idx);
    }
};

struct add_query
{
    ll l, r, c;
    ll k;

    add_query(ll _l, ll _r, ll _c, ll _k)
    {
        l = _l;
        r = _r;
        c = _c;
        k = _k;
    }
};

segment_tree_modified real_val, add_only;
segment_tree st;

ll n, m, q, ans[maxn], ptr[maxn], tf[maxn];
vector < pair < ll, ll > > ask[maxn];
void solve()
{
    cin >> n >> m >> q;
    vector < add_query > vq;
    for (ll i = 1; i <= q; i ++)
    {
        ll type;
        cin >> type;
        if (type == 1)
        {
            ll l, r, c;
            ll k;
            cin >> l >> r >> c >> k;
            add_query aq(l, r, c, k);
            vq.push_back(aq);
            real_val.range_update(1, 1, n, l, r, {0, k});
            add_only.range_update(1, 1, n, l, r, {0, k});
        }
        else if (type == 2)
        {
            ll l, r;
            ll k;
            cin >> l >> r >> k;
            real_val.range_update(1, 1, n, l, r, {k, 0});
        }
        else
        {
            ll a;
            ll b;
            tf[i] = 1;
            cin >> a >> b;
            ll val1 = real_val.query(1, 1, n, a);
            ll val2 = add_only.query(1,1,n, a);
            if (val1 >= b)
            {
                ll idx = val2 - val1 + b;
                ///cout << val1 << " - " << val2 << " - " << b << " - " << idx << endl;
                ask[a].push_back({idx, i});
            }
        }
    }

    for (ll i = 1; i <= n; i ++)
        sort(ask[i].begin(), ask[i].end());


    for (ll i = 1; i <= n; i ++)
    {
        ll val = inf;
        if (!ask[i].empty())
            val = ask[i][0].first;
        st.poll_update(1, 1, n, i, val);
    }

    for (ll i = 0; i < vq.size(); i ++)
    {
        add_query aq = vq[i];
        st.range_update(1, 1, n, aq.l, aq.r, - aq.k);

        while(true)
        {
            st.push_lazy(1, 1, n);
            node nd = st.tree[1];
            if (nd.minx > 0)
                break;
        ///cout << aq.l << " - " << aq.r << " - " << aq.c << " - " << endl;
        ///cout << nd.minx << " " << nd.min_idx << " " << st.query(1, 1, n, 978).minx << " " << ans[39] << endl;
            ll pos = nd.min_idx;
            ans[ask[pos][ptr[pos]].second] = aq.c;

            ///cout << ask[pos][ptr[pos]].second << endl;
            ll val = inf;
            if (ptr[pos] != ((ll)ask[pos].size() - 1))
            {
                val = ask[pos][ptr[pos] + 1].first
                 - ask[pos][ptr[pos]].first;
                ///cout << "HERE " << val << endl;
            }
            st.poll_update(1, 1, n, nd.min_idx, val + nd.minx);
            ptr[pos] ++;
        }
    }

    for (ll i = 1; i <= q; i ++)
        if (tf[i])
            cout << ans[i] << endl;


}

int main()
{
    speed();
    solve();
    return 0;
}
/**

*/

Compilation message (stderr)

foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:258:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<add_query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |     for (ll i = 0; i < vq.size(); i ++)
      |                    ~~^~~~~~~~~~~

• 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