Submission #390891

#	Time	Username	Problem	Language	Result	Execution time	Memory
390891		Jarif_Rahman	Food Court (JOI21_foodcourt)	C++17	0 / 100	1092 ms	30356 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_mx, lazy_add;
        pair<ll, ll> mn, mn2;
        node(){
            sm = 0LL, lazy_mx = -inf, lazy_add = 0LL;
            mn = {0, 1};
            mn2 = {inf, 0};
        }
        void calc(node a, node b){
            sm = a.sm+b.sm;
            vector<pair<ll, ll>> v;
            v.pb(a.mn);
            v.pb(a.mn2);
            if(b.mn.f == v[0].f) v[0].sc+=b.mn.sc;
            else if(b.mn.f == v[1].f) v[1].sc+=b.mn.sc;
            else v.pb(b.mn);
            if(b.mn2.f == v[0].f) v[0].sc+=b.mn2.sc;
            else if(b.mn2.f == v[1].f) v[1].sc+=b.mn2.sc;
            else v.pb(b.mn2);
            sort(v.begin(), v.end());
            mn = v[0];
            mn2 = v[1];
        }
    };
    int k;
    vector<node> v;
    segtree(int n){
        k = 1;
        while(k <= n) k*=2; k*=2;
        v.resize(k, node());
        for(int i = k/2-1; i > 0; i--) v[i].calc(v[2*i], v[2*i+1]);
    }
    void chmx(int l, int r, int nd, int a, int b, ll exs, ll ex, ll x, bool tt){
        if(a > r || b < l || (tt ? ex:v[nd].mn.f+exs) >= x){
            if(tt){
                v[nd].lazy_mx = ex;
                v[nd].lazy_add+=exs;
                v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(ex-v[nd].mn.f);
                v[nd].mn.f = ex;
            }
            else{
                if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=exs;
                v[nd].lazy_add+=exs;
                v[nd].sm+=(b-a+1)*exs;
                v[nd].mn.f+=exs;
                if(v[nd].mn2.f != inf) v[nd].mn2.f+=exs;
            }
            return;
        }
        if(a >= l && b <= r && v[nd].mn2.f+exs > x){
            v[nd].lazy_mx = x;
            v[nd].lazy_add+=exs;
            v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(x-v[nd].mn.f);
            v[nd].mn.f = x;
            return;
        }
        exs+=v[nd].lazy_add;
        if(!tt){
            if(v[nd].lazy_mx != -inf){
                tt = 1;
                ex+=v[nd].lazy_mx;
            }
        }
        if(!tt){
            ex+=v[nd].lazy_add;
        }
        v[nd].lazy_mx = -inf;
        v[nd].lazy_add = 0LL;
        int md = (a+b)/2;
        chmx(l, r, 2*nd, a, md, exs, ex, x, tt);
        chmx(l, r, 2*nd+1, md+1, b, exs, ex, x, 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, 0, 0, x, 0);
    }
    void add(int l, int r, int nd, int a, int b, ll exs, ll ex, ll x, bool tt){
        if(a > r || b < l){
            if(tt){
                v[nd].lazy_mx = ex;
                v[nd].lazy_add+=exs;
                v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(ex-v[nd].mn.f);
                v[nd].mn.f = ex;
            }
            else{
                if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=exs;
                v[nd].lazy_add+=exs;
                v[nd].sm+=(b-a+1)*exs;
                v[nd].mn.f+=exs;
                if(v[nd].mn2.f != inf) v[nd].mn2.f+=exs;
            }
            return;
        }
        if(a >= l && b <= r){
            if(tt){
                v[nd].lazy_mx = ex;
                v[nd].lazy_add+=exs;
                v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(ex-v[nd].mn.f);
                v[nd].mn.f = ex;
            }
            else{
                if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=exs;
                v[nd].lazy_add+=exs;
                v[nd].sm+=(b-a+1)*exs;
                v[nd].mn.f+=exs;
                if(v[nd].mn2.f != inf) v[nd].mn2.f+=exs;
            }
            if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=x;
            v[nd].lazy_add+=x;
            v[nd].sm+=(b-a+1)*x;
            v[nd].mn.f+=x;
            if(v[nd].mn2.f != inf) v[nd].mn2.f+=x;
            return;
        }
        exs+=v[nd].lazy_add;
        if(!tt){
            if(v[nd].lazy_mx != -inf){
                tt = 1;
                ex+=v[nd].lazy_mx;
            }
        }
        if(!tt){
            ex+=v[nd].lazy_add;
        }
        v[nd].lazy_mx = -inf;
        v[nd].lazy_add = 0LL;
        int md = (a+b)/2;
        add(l, r, 2*nd, a, md, exs, ex, x, tt);
        add(l, r, 2*nd+1, md+1, b, exs, ex, x, 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, 0, 0, x, 0);
    }
    ll sum(int l, int r, int nd, int a, int b, ll exs, ll ex, bool tt){
        if(a > r || b < l){
            if(tt){
                v[nd].lazy_mx = ex;
                v[nd].lazy_add+=exs;
                v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(ex-v[nd].mn.f);
                v[nd].mn.f = ex;
            }
            else{
                if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=exs;
                v[nd].lazy_add+=exs;
                v[nd].sm+=(b-a+1)*exs;
                v[nd].mn.f+=exs;
                if(v[nd].mn2.f != inf) v[nd].mn2.f+=exs;
            }
            return 0LL;
        }
        if(a >= l && b <= r){
            if(tt){
                v[nd].lazy_mx = ex;
                v[nd].lazy_add+=exs;
                v[nd].sm+=(b-a+1-v[nd].mn.sc)*exs + v[nd].mn.sc*(ex-v[nd].mn.f);
                v[nd].mn.f = ex;
            }
            else{
                if(v[nd].lazy_mx != -inf) v[nd].lazy_mx+=exs;
                v[nd].lazy_add+=exs;
                v[nd].sm+=(b-a+1)*exs;
                v[nd].mn.f+=exs;
                if(v[nd].mn2.f != inf) v[nd].mn2.f+=exs;
            }
            return v[nd].sm;
        }
        exs+=v[nd].lazy_add;
        if(!tt){
            if(v[nd].lazy_mx != -inf){
                tt = 1;
                ex+=v[nd].lazy_mx;
            }
        }
        if(!tt){
            ex+=v[nd].lazy_add;
        }
        v[nd].lazy_mx = -inf;
        v[nd].lazy_add = 0LL;
        int md = (a+b)/2;
        ll rt = sum(l, r, 2*nd, a, md, exs, ex, tt) + sum(l, r, 2*nd+1, md+1, b, exs, 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, 0, 0, 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:38:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   38 |         while(k <= n) k*=2; k*=2;
      |         ^~~~~
foodcourt.cpp:38:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   38 |         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