Submission #399469

#	Time	Username	Problem	Language	Result	Execution time	Memory
399469		534351	Food Court (JOI21_foodcourt)	C++17	0 / 100	1088 ms	23236 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

const int MAXN = 250013;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

//a lazy can either say:
//1) increase everything by a value
//2) set everything to a value

int N, M, Q;
ll segmin[3 * MAXN], segmax[3 * MAXN];
pair<bool, ll> lazy[3 * MAXN]; //we need to store min?

void push(int w, int L, int R)
{
    if (lazy[w] == MP(false, 0ll)) return;
    if (lazy[w].fi) //set everything to this value.
    {
        ll v = lazy[w].se;
        segmin[w] = v;
        segmax[w] = v;
        if (L != R)
        {
            lazy[w << 1] = lazy[w];
            lazy[w << 1 | 1] = lazy[w];
        }
    }
    else //increase everything by a value.
    {
        ll v = lazy[w].se;
        segmin[w] += v;
        segmax[w] += v;
        if (L != R)
        {
            lazy[w << 1].se += lazy[w].se;
            lazy[w << 1 | 1].se += lazy[w].se;
        }
    }
    lazy[w] = {false, 0};
    return;
}
void update(int w, int L, int R, int a, int b, ll v)
{
    push(w, L, R);
    if (b < L || R < a)
    {
        return;
    }
    if (a <= L && R <= b)
    {
        if (segmin[w] + v >= 0 && segmax[w] + v >= 0)
        {
            lazy[w].se += v;
            push(w, L, R);
            return;
        }
        else if (segmin[w] + v <= 0 && segmax[w] + v <= 0)
        {
            lazy[w] = {true, 0};
            push(w, L, R);
            return;
        }
    }
    int mid = (L + R) >> 1;
    update(w << 1, L, mid, a, b, v);
    update(w << 1 | 1, mid + 1, R, a, b, v);
    segmin[w] = min(segmin[w << 1], segmin[w << 1 | 1]);
    segmax[w] = max(segmax[w << 1], segmax[w << 1 | 1]);
}
ll query(int w, int L, int R, int a)
{
    push(w, L, R);
    if (L == R)
    {
        return segmin[w];
    }
    int mid = (L + R) >> 1;
    if (a <= mid) return query(w << 1, L, mid, a);
    else return query(w << 1 | 1, mid + 1, R, a);
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    cin >> N >> M >> Q;
    while(Q--)
    {
        int qid;
        cin >> qid;
        if (qid == 1)
        {
            //join.
            int l, r, c; ll k;
            cin >> l >> r >> c >> k; l--; r--;
            update(1, 0, N - 1, l, r, k);
        }
        if (qid == 2)
        {
            int l, r; ll k;
            cin >> l >> r >> k; l--; r--;
            update(1, 0, N - 1, l, r, -k);
        }
        if (qid == 3)
        {
            int a; ll b;
            cin >> a >> b; a--;
            ll c = query(1, 0, N - 1, a);
            cout << ((c >= b) ? 1 : 0) << '\n';
        }
    }
    return 0;
}

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