Submission #1144046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144046		hmm789	Weirdtree (RMI21_weirdtree)	C++20	100 / 100	590 ms	42428 KiB

weirdtree

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

int a[300001];

struct seg {
    int mx, cnt, smx;
    long long sm;
};

struct node {
    int s, e, m, lz;
    seg v;
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2;
        if(s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
            v = merge(l->v, r->v);
        } else {
            v.sm = v.mx = a[s];
            v.cnt = 1; v.smx = -1;
        }
    }
    seg merge(seg a, seg b) {
        seg ans;
        ans.sm = a.sm + b.sm;
        ans.mx = max(a.mx, b.mx);
        if(a.mx == b.mx) {
            ans.cnt = a.cnt + b.cnt;
            ans.smx = max(a.smx, b.smx);
        } else if(a.mx > b.mx) {
            ans.cnt = a.cnt;
            ans.smx = max(a.smx, b.mx);
        } else {
            ans.cnt = b.cnt;
            ans.smx = max(a.mx, b.smx);
        }
        return ans;
    }
    void prop() {
        if(s == e) return;
        int mxx = max(l->v.mx, r->v.mx);
        if(l->v.mx == mxx) {
            l->v.sm += l->v.cnt * lz;
            l->v.mx += lz;
            l->lz += lz;
        }
        if(r->v.mx == mxx) {
            r->v.sm += r->v.cnt * lz;
            r->v.mx += lz;
            r->lz += lz;
        }
        lz = 0;
    }
    void chmin(int x, int y, int val) {
        prop();
        if(val >= v.mx) return;
        if(x <= s && e <= y && val > v.smx) {
            lz += val-v.mx;
            v.sm += (val-v.mx) * v.cnt;
            v.mx = val; return;
        } else if(x > m) r->chmin(x, y, val);
        else if(y <= m) l->chmin(x, y, val);
        else l->chmin(x, y, val), r->chmin(x, y, val);
        v = merge(l->v, r->v);
    }
    void update(int x, int val) {
        prop();
        if(s == e) {
            lz += val-v.mx;
            v.sm += val-v.mx;
            v.mx = val; return;
        } else if(x > m) r->update(x, val);
        else l->update(x, val);
        v = merge(l->v, r->v);
    }
    seg query(int x, int y) {
        prop();
        if(x <= s && e <= y) return v;
        else if(x > m) return r->query(x, y);
        else if(y <= m) return l->query(x, y);
        else return merge(l->query(x, y), r->query(x, y));
    }
    int bsta(int x, int val, int &num) {
        prop();
        if(s == e) {
            num -= v.mx == val;
            return s;
        }
        if(x > m) return r->bsta(x, val, num);
        else if(s < x || l->v.mx > val) {
            int res = l->bsta(x, val, num);
            if(num <= 0) return res;
            else return r->bsta(x, val, num);
        } else if(l->v.mx < val) return r->bsta(x, val, num);
        else if(l->v.cnt < num) {
            num -= l->v.cnt;
            return r->bsta(x, val, num);
        } else return l->bsta(x, val, num);
    }
} *root;

void initialise(int N, int Q, int h[]) {
    for(int i = 1; i <= N; i++) a[i] = h[i];
    root = new node(1, N);
}
void cut(int l, int r, int k) {
    while(k) {
        seg res = root->query(l, r);
        res.smx = max(res.smx, 0);
        if(res.mx == 0) break;
        if((long long)(res.mx-res.smx) * res.cnt <= k) {
            k -= (long long)(res.mx-res.smx) * res.cnt;
            root->chmin(l, r, res.smx);
        } else {
            int sub = k/res.cnt, num = k % res.cnt;
            if(num == 0) {
                root->chmin(l, r, res.mx - sub);
            }
            else {
                int idx = root->bsta(l, res.mx, num);
                root->chmin(l, idx, res.mx - sub - 1);
                root->chmin(idx+1, r, res.mx - sub);
            }
            break;
        }
    }
}
void magic(int i, int x) {
    root->update(i, x);
}
long long int inspect(int l, int r) {
    return root->query(l, r).sm;
}

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