Submission #852668

#	Time	Username	Problem	Language	Result	Execution time	Memory
852668		danikoynov	Food Court (JOI21_foodcourt)	C++14	100 / 100	372 ms	57232 KiB

foodcourt

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

**/

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

using namespace std;
typedef long long ll;

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

const ll maxn = 250010;
const ll inf = 1e18;

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

    pair < ll, ll > merge_lazy(pair < ll, ll > a, pair < ll, ll > b)
    {
        ll c = min(a.second, b.first);
        a.second -= c;
        b.first -= c;
        a.first += b.first;
        a.second += b.second;
        return a;
    }

    void push_lazy(ll root, ll left, ll right)
    {

        tree[root] -= lazy[root].first;
        tree[root] = max(tree[root], (ll)(0));
        tree[root] += lazy[root].second;

        if (left != right)
        {
            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 update(ll root, ll left, ll right, ll qleft, ll qright, pair < ll, ll > cur)
    {

        push_lazy(root, left, right);

        if (left > qright || right < qleft)
            return;

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

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

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


    }

    ll query(ll root, ll left, ll right, int pos)
    {

        push_lazy(root, left, right);

        if (left == right)
            return tree[root];

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

};
ll readInt()
{
    bool minus = false;
    ll result = 0;
    char ch;
    ch = getchar();
    while (true)
    {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus = true;
    else result = ch-'0';
    while (true)
    {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus)
        return -result;
    else
        return result;
}


long long read_int()
{
    char r;
    bool start=false,neg=false;
    long long ret=0;
    while(true)
    {
        r=getchar();
        if((r-'0'<0 || r-'0'>9) && r!='-' && !start)
        {
            continue;
        }
        if((r-'0'<0 || r-'0'>9) && r!='-' && start)
        {
            break;
        }
        if(start)ret*=10;
        start=true;
        if(r=='-')neg=true;
        else ret+=r-'0';
    }
    if(!neg)
        return ret;
    else
        return -ret;
}

ll n, m, q;
void input()
{
    n = readInt();
    m = readInt();
    q = readInt();
    //cin >> n >> m >> q;
}

struct task
{
    ll idx;
    ll  pos;

    task(ll _idx = 0, ll _pos = 0)
    {
        idx = _idx;

        pos = _pos;
    }
};

struct bit
{
    ll fen[maxn];

    void update(ll pos, ll val)
    {
        for (ll i = pos; i < maxn; i += (i & -i))
            fen[i] += val;
    }

    ll query(ll pos)
    {
        ll sum = 0;
        for (ll i = pos; i > 0; i -= (i & -i))
            sum += fen[i];
        return sum;
    }

    void range_update(ll l, ll r, ll v)
    {
        update(l, v);
        update(r + 1, - v);
    }

    ll find_kth(ll to)
    {
        ll pos = 0;
        ll sum = 0;
        for (ll bit = 20; bit >= 0; bit --)
        {
            if (pos + (1 << bit) > maxn)
                continue;
            ll new_sum = sum + fen[pos + (1 << bit)];
            if (new_sum < to)
            {
                pos = pos + (1 << bit);
                sum = new_sum;
            }
        }
        return pos + 1;
    }
};

vector < task > ask[maxn];
segment_tree line_tree;
bit pass_tree;
ll ans[maxn];


pair < int, ll > add[maxn];
vector < ll > upd[maxn];
ll query_cnt = 0;

void simulate()
{

    ll t, l, r, c, a; /// careful overflow
    ll k, b;

    ll cnt = 0;
    ll last = 0;
    for (ll i = 1; i <= q; i ++)
    {

        t = readInt();
        if (t == 1)
        {
            ///cin >> l >> r >> c >> k;
            l = readInt();
            r = readInt();
            c = readInt();
            k = read_int();
            line_tree.update(1, 1, n, l, r, {0, k});
            pass_tree.range_update(l, r, k);
            add[i] = {c, k};
            upd[l].push_back(i);
            upd[r + 1].push_back(-i);
        }
        else if (t == 2)
        {
            ///cin >> l >> r >> k;
            l = readInt();
            r = readInt();
            k = read_int();

            line_tree.update(1, 1, n, l, r, {k, 0});




        }
        else
        {
            ///cin >> a >> b;
            a = readInt();
            b = read_int();
            query_cnt ++;
            ll act = line_tree.query(1, 1, n, a);
            if (act < b)
            {
                ans[query_cnt] = 0;
            }
            else
            {
                ///cout << "here " << query_cnt << " " << pass_tree.query(a) << " " << act << endl;
                ask[a].push_back(task(query_cnt, pass_tree.query(a) - act + b));
            }
        }
    }


}

bit active;
void answer_tasks()
{

    for (ll i = 1; i <= n; i ++)
    {
        for (ll cur : upd[i])
        {
            if (cur > 0)
            {
                active.update(cur, add[cur].second);
            }
            else
            {
                active.update(-cur, - add[-cur].second);
            }
        }

        for (task cur : ask[i])
        {
            ans[cur.idx] = add[active.find_kth(cur.pos)].first;
            ///cout << cur.idx << " : " << cur.shop << " " << cur.pos << endl;
        }
    }
    for (ll i = 1; i <= query_cnt; i ++)
    {
        cout << ans[i] << endl;
    }
}

void solve()
{
    input();
    simulate();
    answer_tasks();
}

int main()
{
    ///freopen("test.txt", "r", stdin);
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In member function 'll segment_tree::query(ll, ll, ll, int)':
foodcourt.cpp:90:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   90 |         if (pos <= mid)
      |         ^~
foodcourt.cpp:92:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   92 |             return query(root * 2 + 1, mid + 1, right, pos);
      |             ^~~~~~
foodcourt.cpp: In function 'void simulate()':
foodcourt.cpp:231:8: warning: unused variable 'cnt' [-Wunused-variable]
  231 |     ll cnt = 0;
      |        ^~~
foodcourt.cpp:232:8: warning: unused variable 'last' [-Wunused-variable]
  232 |     ll last = 0;
      |        ^~~~

• 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