Submission #387218

#	Time	Username	Problem	Language	Result	Execution time	Memory
387218		Jarif_Rahman	Food Court (JOI21_foodcourt)	C++17	0 / 100	1080 ms	27372 KiB

foodcourt

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
struct segtree{
    struct node{
        ll sm, lazy_assign, lazy_add, mx, mn;
        node(){
            sm = 0LL, mx = 0LL, mn = 0LL, lazy_assign = -inf, lazy_add = 0LL;
        }
        void calc(node a, node b){
            sm = a.sm+b.sm;
            mx = max(a.mx, b.mx);
            mn = min(a.mn, b.mn);
        }
    };
    int k;
    vector<node> v;
    segtree(int n){
        k = 1;
        while(k <= n) k*=2; k*=2;
        v.resize(k, node());
    }
    void chmx(int l, int r, int nd, int a, int b, ll x, ll ex, bool tt){
        if(a > r || b < l || (tt ? ex:v[nd].mn+ex) >= x){
            if(tt){
                v[nd].lazy_assign = ex;
                v[nd].lazy_add = 0LL;
                v[nd].sm = (b-a+1)*ex;
                v[nd].mn = ex;
                v[nd].mx = ex;
            }
            else{
                v[nd].lazy_add+=ex;
                v[nd].sm+=(b-a+1)*ex;
                v[nd].mn+=ex;
                v[nd].mx+=ex;
            }
            return;
        }
        if(a >= l && b <= r && (tt ? ex:v[nd].mx+ex) < x){
            v[nd].lazy_assign = x;
            v[nd].lazy_add = 0LL;
            v[nd].sm = (b-a+1)*x;
            v[nd].mn = x;
            v[nd].mx = x;
            return;
        }
        int md = (a+b)/2;
        if(!tt){
            ex+=v[nd].lazy_add;
            if(v[nd].lazy_assign != -inf){
                ex+=v[nd].lazy_assign;
                tt = 1;
            }
        }
        v[nd].lazy_add = 0LL;
        v[nd].lazy_assign = -inf;
        chmx(l, r, 2*nd, a, md, x, ex, tt);
        chmx(l, r, 2*nd+1, md+1, b, x, ex, tt);
        if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
    }
    void chmx(int l, int r, ll x){
        chmx(l, r, 1, 0, k/2-1, x, 0LL, 0);
    }
    void add(int l, int r, int nd, int a, int b, ll x, ll ex, bool tt){
        if(a > r || b < l){
            if(tt){
                v[nd].lazy_assign = ex;
                v[nd].lazy_add = 0LL;
                v[nd].sm = (b-a+1)*ex;
                v[nd].mn = ex;
                v[nd].mx = ex;
            }
            else{
                v[nd].lazy_add+=ex;
                v[nd].sm+=(b-a+1)*ex;
                v[nd].mn+=ex;
                v[nd].mx+=ex;
            }
            return;
        }
        if(a >= l && b <= r){
            if(tt){
                v[nd].lazy_assign = ex;
                v[nd].lazy_add = 0LL;
                v[nd].sm = (b-a+1)*ex;
                v[nd].mn = ex;
                v[nd].mx = ex;
            }
            else{
                v[nd].lazy_add+=ex;
                v[nd].sm+=(b-a+1)*ex;
                v[nd].mn+=ex;
                v[nd].mx+=ex;
            }
            v[nd].lazy_add+=x;
            v[nd].sm+=(b-a+1)*x;
            v[nd].mn+=x;
            v[nd].mx+=x;
            return;
        }
        int md = (a+b)/2;
        if(!tt){
            ex+=v[nd].lazy_add;
            if(v[nd].lazy_assign != -inf){
                ex+=v[nd].lazy_assign;
                tt = 1;
            }
        }
        v[nd].lazy_add = 0LL;
        v[nd].lazy_assign = -inf;
        add(l, r, 2*nd, a, md, x, ex, tt);
        add(l, r, 2*nd+1, md+1, b, x, ex, tt);
        if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
    }
    void add(int l, int r, ll x){
        add(l, r, 1, 0, k/2-1, x, 0LL, 0);
    }
    ll sum(int l, int r, int nd, int a, int b, ll ex, bool tt){
        if(a > r || b < l){
            if(tt){
                v[nd].lazy_assign = ex;
                v[nd].lazy_add = 0LL;
                v[nd].sm = (b-a+1)*ex;
                v[nd].mn = ex;
                v[nd].mx = ex;
            }
            else{
                v[nd].lazy_add+=ex;
                v[nd].sm+=(b-a+1)*ex;
                v[nd].mn+=ex;
                v[nd].mx+=ex;
            }
            return 0LL;
        }
        if(a >= l && b <= r){
            if(tt){
                v[nd].lazy_assign = ex;
                v[nd].lazy_add = 0LL;
                v[nd].sm = (b-a+1)*ex;
                v[nd].mn = ex;
                v[nd].mx = ex;
            }
            else{
                v[nd].lazy_add+=ex;
                v[nd].sm+=(b-a+1)*ex;
                v[nd].mn+=ex;
                v[nd].mx+=ex;
            }
            return v[nd].sm;
        }
        int md = (a+b)/2;
        if(!tt){
            ex+=v[nd].lazy_add;
            if(v[nd].lazy_assign != -inf){
                ex+=v[nd].lazy_assign;
                tt = 1;
            }
        }
        v[nd].lazy_add = 0LL;
        v[nd].lazy_assign = -inf;
        ll rt = sum(l, r, 2*nd, a, md, ex, tt) + sum(l, r, 2*nd+1, md+1, b, ex, tt);
        if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
        return rt;
    }
    ll sum(int l, int r){
        return sum(l, r, 1, 0, k/2-1, 0LL, 0);
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
    segtree seg(n);
    while(q--){
        int tt; cin >> tt;
        if(tt == 1){
            int l, r, c; ll k; cin >> l >> r >> c >> k; l--, r--;
            seg.add(l, r, k);
        }
        else if(tt == 2){
            int l, r; ll k; cin >> l >> r >> k; l--, r--;
            seg.add(l, r, -k);
            seg.chmx(0, seg.k/2-1, 0);
        }
        else{
            int a; ll b; cin >> a >> b; a--;
            cout << (seg.sum(a, a) >= b ? 1:0) << "\n";
        }
    }
}

Compilation message (stderr)

foodcourt.cpp: In constructor 'segtree::segtree(int)':
foodcourt.cpp:25:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   25 |         while(k <= n) k*=2; k*=2;
      |         ^~~~~
foodcourt.cpp:25:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   25 |         while(k <= n) k*=2; k*=2;
      |                             ^

• 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