Submission #870485

#	Time	Username	Problem	Language	Result	Execution time	Memory
870485		garam1732	Food Court (JOI21_foodcourt)	C++14	21 / 100	296 ms	39504 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define bl " "
#define endl "\n"
#define all(v) v.begin(), v.end()
#define comp(v) v.erase(unique(all(v)), v.end())
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 250250;
const int MOD = 998244353;

vector<pll> tree, lazy;

void prop(pll &x, pll &y) {
    x.ff += y.ff;
    x.ss = max(x.ss+y.ff, y.ss);
}

void update_lazy(int node, int s, int e) {
    if(lazy[node].ff || lazy[node].ss) {
        prop(tree[node], lazy[node]);

        if(s != e) {
            prop(lazy[node<<1], lazy[node]);
            prop(lazy[node<<1|1], lazy[node]);
        }

        lazy[node] = pll(0, 0);
    }
}

void update(int node, int s, int e, int l, int r, pll v) {
    update_lazy(node, s, e);
    if(e < l || r < s) return;
    if(l <= s && e <= r) {
        prop(lazy[node], v);
        update_lazy(node, s, e);
        return;
    }

    int mid = s+e>>1;
    update(node<<1, s, mid, l, r, v); update(node<<1|1, mid+1, e, l, r, v);
}

void solve(int node, int s, int e, int idx, ll &x) {
    update_lazy(node, s, e);
    if(e < idx || idx < s) return;
    if(s == e) {
        x = max(tree[node].ff, tree[node].ss);
        return;
    }

    int mid = s+e>>1;
    solve(node<<1, s, mid, idx, x); solve(node<<1|1, mid+1, e, idx, x);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n, m, q; cin >> n >> m >> q;
    tree.resize(1 << 20); lazy.resize(1 << 20);

    while(q--) {
        int t; cin >> t;
        if(t == 1) {
            int l, r, c, k; cin >> l >> r >> c >> k;
            update(1, 1, n, l, r, pll(k, 0));
        }
        else if(t == 2) {
            int l, r, k; cin >> l >> r >> k;
            update(1, 1, n, l, r, pll(-k, 0));
        }
        else {
            int a; ll b; cin >> a >> b;
            ll x; solve(1, 1, n, a, x);
            //cout<<x<<endl;
            cout << (x >= b ? 1 : 0) << endl;
        }
    }
}

Compilation message (stderr)

foodcourt.cpp: In function 'void update(int, int, int, int, int, pll)':
foodcourt.cpp:47:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int mid = s+e>>1;
      |               ~^~
foodcourt.cpp: In function 'void solve(int, int, int, int, ll&)':
foodcourt.cpp:59:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = s+e>>1;
      |               ~^~

• 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