Submission #495372

#	Time	Username	Problem	Language	Result	Execution time	Memory
495372		danikoynov	Food Court (JOI21_foodcourt)	C++14	21 / 100	762 ms	17912 KiB

foodcourt

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

**/

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

using namespace std;
typedef long long ll;
const int maxn = 250010;

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



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(int root, int left, int 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(int root, int left, int right, int qleft, int 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;
    }

    int 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(int root, int left, int right, int idx)
{
    ///cout << left << " - " << right << " " << lazy[root].first << " " << lazy[root].second << endl;
    push_lazy(root, left, right);
    if (left == right)
        return tree[root];

    int mid = (left + right) /2;
    if (idx <= mid)
        return query(root * 2, left, mid, idx);
    return query(root * 2 + 1, mid + 1, right, idx);
}
int n, m, q;
void solve()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i ++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int l, r, c;
            ll k;
            cin >> l >> r >> c >> k;
            range_update(1, 1, n, l, r, {0, k});
        }
        else
        if (type == 2)
        {
            int l, r;
            ll k;
            cin >> l >> r >> k;
            range_update(1, 1, n, l, r, {k, 0});
        }
        else
        {
            int a;
            ll b;
            cin >> a >> b;
            ll val = query(1, 1, n, a);
            if (val >= b)
                cout << 1 << endl;
            else
                cout << 0 << endl;
        }

    }

}

int main()
{
    solve();
    return 0;
}

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