Submission #1126244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126244		dwuy	Weirdtree (RMI21_weirdtree)	C++20	0 / 100	2096 ms	45372 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct Node{
    ll fm, sm, cm, lz, sum;
    Node() : fm(0), sm(-2), cm(0), sum(0) {}
};

struct SMT{
    ll n;
    vector<Node> tree;
    SMT(ll n = 0) : n(n), tree(n<<2|3, Node()) {};

    void down(ll id){
        if(tree[id].lz == 0) return;
        ll delta = tree[id].lz;
        tree[id<<1].lz += delta;
        tree[id<<1].fm += delta;
        tree[id<<1].sum += delta * tree[id<<1].cm;
        tree[id<<1|1].lz += delta;
        tree[id<<1|1].fm += delta;
        tree[id<<1|1].sum += delta * tree[id<<1|1].cm;
        tree[id].lz = 0;
    }

    void update(ll id){
        Node &L = tree[id<<1];
        Node &R = tree[id<<1|1];
        tree[id].sum = L.sum + R.sum;
        tree[id].fm = max(L.fm, R.fm);
        tree[id].cm = 0;
        if(tree[id].fm == L.fm) tree[id].cm += L.cm;
        if(tree[id].fm == R.fm) tree[id].cm += R.cm;
        if(L.fm != R.fm) tree[id].sm = min(L.fm, R.fm);
        else tree[id].sm = max(L.sm, R.sm);
    }

    void assign(ll pos, ll val){
        ll id = 1;
        for(ll lo=1, hi=n; lo<hi;){
            ll mid = (lo + hi)>>1;
            down(id);
            if(pos <= mid) id = id<<1, hi = mid;
            else lo = mid + 1, id = id<<1 | 1;
        }
        tree[id].fm = tree[id].sum = val;
        tree[id].cm = 1;
        for(id>>=1; id; id>>=1) update(id);
    }

    ll gmax(ll l, ll r, ll id, const ll &u, const ll &v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return tree[id].fm;
        down(id);
        ll mid = (l + r)>>1;
        return max(gmax(l, mid, id<<1, u, v), gmax(mid + 1, r, id<<1|1, u, v));
    }

    ll gmax(ll l, ll r){
        return gmax(1, n, 1, l, r);
    }

    ll gsum(ll l, ll r, ll id, const ll &u, const ll &v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return tree[id].sum;
        ll mid = (l + r)>>1;
        return gsum(l, mid, id<<1, u, v) + gsum(mid + 1, r, id<<1|1, u, v);
    }

    ll gsum(ll l, ll r){
        return gsum(1, n, 1, l, r);
    }

    ll gmid(ll l, ll r, ll id, const ll &u, const ll &v, const ll &val){
        if(l > v || r < u || tree[id].fm <= val) return 0;
        // cout << " === " << l << ' ' << r << ' ' << tree[id].fm << ' ' << tree[id].cm << '\n';
        if(l >= u && r <= v && tree[id].sm < val) return tree[id].cm*(tree[id].fm - val);
        down(id);
        ll mid = (l + r)>>1;
        return gmid(l, mid, id<<1, u, v, val) + gmid(mid + 1, r, id<<1|1, u, v, val);
    }

    ll gmid(ll l, ll r, ll val){
        return gmid(1, n, 1, l, r, val);
    }

    void zmin(ll l, ll r, ll id, const ll &u, const ll &v, const ll &val){
        if(l > v || r < u || tree[id].fm <= val) return;
        if(l >= u && r <= v && tree[id].sm < val){
            tree[id].sum -= tree[id].cm * (tree[id].fm - val);
            tree[id].lz += val - tree[id].fm;
            tree[id].fm = val;
            return;
        }
        down(id);
        ll mid = (l + r)>>1;
        zmin(l, mid, id<<1, u, v, val);
        zmin(mid + 1, r, id<<1|1, u, v, val);
        update(id);
    }
    
    void zmin(ll l, ll r, ll val){
        zmin(1, n, 1, l, r, val);
    }

    void pmin(ll l, ll r, ll id, const ll &u, const ll &v, const ll &mx, ll &k){
        if(l > v || r < u || k == 0 || tree[id].fm < mx) return;
        if(l >= u && r <= v && tree[id].sm < tree[id].fm - 1 && tree[id].fm == mx && tree[id].cm <= k){
            k -= tree[id].cm;
            tree[id].sum -= tree[id].cm;
            tree[id].lz += -1;
            tree[id].fm--;
            return;
        }
        down(id);
        ll mid = (l + r)>>1;
        pmin(l, mid, id<<1, u, v, mx, k);
        pmin(mid + 1, r, id<<1|1, u, v, mx, k);
        update(id);   
    }

    void pmin(ll l, ll r, ll k){
        pmin(1, n, 1, l, r, gmax(l, r), k);
    }
} smt;

ll n, q;
void initialise(int N, int Q, int h[]){
    n = N;
    q = Q;
    smt = SMT(n);
    for(ll i=1; i<=n; i++) smt.assign(i, h[i]);
}

void cut(int l, int r, int k){
    ll pos = -1;
    ll pre = 0;
    for(ll lo=1, hi=smt.gmax(l, r); lo<=hi;){
        ll mid = (lo + hi)>>1;
        ll cnt = smt.gmid(l, r, mid);
        if(cnt <= k){
            pre = cnt;
            pos = mid;
            hi = mid - 1;
        }
        else lo = mid + 1;
    }
    smt.zmin(l, r, pos);
    smt.pmin(l, r, k - pre);
}

void magic(int p, int x){
    smt.assign(p, x);
}

ll inspect(int l, int r){
    return smt.gsum(l, r);
}

/*

 6 10
 1 2 3 1 2 3
 1 1 6 3
 3 1 6
 1 1 3 3
 3 1 6
 1 1 3 1000
 3 1 6
 2 1 1000
 3 1 6
 1 1 3 999
 3 1 5

 6 4
 1 2 3 1 2 3
 1 1 6 3
 3 1 6
 1 1 3 3
 3 1 6


 1 2 3 1 2 3
 1 1 2 1 2 2
 0 0 1 1 2 2

*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29