Submission #1125968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125968		Zero_OP	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	404 ms	28300 KiB

weirdtree

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct segment_tree_beat{
    int N;
    vector<int> mx, mx2, cnt_mx;
    vector<ll> sum;

    segment_tree_beat() : mx(), mx2(), cnt_mx(), sum() {}
    segment_tree_beat(int n) : N(n), mx(n << 2), mx2(n << 2), cnt_mx(n << 2), sum(n << 2) {}

    void pull(int id){
        sum[id] = sum[id << 1] + sum[id << 1 | 1];

        if(mx[id << 1] == mx[id << 1 | 1]){
            mx[id] = mx[id << 1];
            mx2[id] = max(mx2[id << 1], mx2[id << 1 | 1]);
            cnt_mx[id] = cnt_mx[id << 1] + cnt_mx[id << 1 | 1];
        } else if(mx[id << 1] > mx[id << 1 | 1]){
            mx[id] = mx[id << 1];
            mx2[id] = max(mx2[id << 1], mx[id << 1 | 1]);
            cnt_mx[id] = cnt_mx[id << 1];
        } else{
            mx[id] = mx[id << 1 | 1];
            mx2[id] = max(mx[id << 1], mx2[id << 1 | 1]);
            cnt_mx[id] = cnt_mx[id << 1 | 1];
        }
    }

    void chmin(int id, int l, int r, int val){
        if(mx[id] <= val) return;
        assert(mx2[id] < val);

        sum[id] -= 1LL * (mx[id] - val) * cnt_mx[id];
        mx[id] = val;
    }

    void down(int id, int l, int r, int mid){
        chmin(id << 1, l, mid, mx[id]);
        chmin(id << 1 | 1, mid + 1, r, mx[id]);
    }

    void build(int id, int l, int r, const vector<int>& A){
        if(l == r){
            mx[id] = A[l];
            mx2[id] = -1;
            cnt_mx[id] = 1;
            sum[id] = A[l];
        } else{
            int mid = l + r >> 1;
            build(id << 1, l, mid, A);
            build(id << 1 | 1, mid + 1, r, A);
            pull(id);
        }
    }

    void change(int id, int l, int r, int pos, int val){
        if(l == r){
            mx[id] = val;
            sum[id] = val;
        } else{
            int mid = l + r >> 1;
            down(id, l, r, mid);
            if(pos <= mid) change(id << 1, l, mid, pos, val);
            else change(id << 1 | 1, mid + 1, r, pos, val);
            pull(id);
        }
    }

    void chmin(int id, int l, int r, int u, int v, int val){
        if(v < l || u > r || mx[id] <= val) return;
        if(u <= l && r <= v && mx2[id] < val) chmin(id, l, r, val);
        else{
            int mid = l + r >> 1;
            chmin(id << 1, l, mid, u, v, val);
            chmin(id << 1 | 1, mid + 1, r, u, v, val);
            pull(id);
        }
    }

    long long query(int id, int l, int r, int u, int v){
        if(v < l || u > r) return 0;
        if(u <= l && r <= v) return sum[id];
        int mid = l + r >> 1;
        down(id, l, r, mid);
        return query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v);
    }

int a, b, c;

    void rec(int id, int l, int r, int u, int v){
        if(u <= l && r <= v){
            if(a == mx[id]){
                c += cnt_mx[id];
                b = max(b, mx2[id]);
            } else if(a > mx[id]){
                b = max(b, mx[id]);
            } else{
                b = max(mx2[id], a);
                a = mx[id];
                c = cnt_mx[id];
            }
        } else{
            int mid = l + r >> 1;
            down(id, l, r, mid);
            if(u <= mid) rec(id << 1, l, mid, u, v);
            if(mid < v)  rec(id << 1 | 1, mid + 1, r, u, v);
        }
    }

    tuple<int, int, int> get_info(int l, int r){
        a = 0, b = 0, c = 0;
        rec(1, 0, N - 1, l, r);
        return make_tuple(a, b, c);
    }

    int walk(int id, int l, int r, int k){
        if(l == r) return l;
        int mid = l + r >> 1;
        down(id, l, r, mid);
        if(mx[id << 1] == mx[id << 1 | 1]){
            if(k - cnt_mx[id << 1] > 0) return walk(id << 1 | 1, mid + 1, r, k - cnt_mx[id << 1]);
            else return walk(id << 1, l, mid, k);
        } else if(mx[id << 1] > mx[id << 1 | 1]){
            return walk(id << 1, l, mid, k);
        } else{
            return walk(id << 1 | 1, mid + 1, r, k);
        }

        assert(false);
    }

    void search_info(int id, int l, int r, int u, int v, vector<tuple<int, int, int>>& info){
        if(u <= l && r <= v){
            info.emplace_back(id, l, r);
        } else{
            int mid = l + r >> 1;
            down(id, l, r, mid);
            if(u <= mid) search_info(id << 1, l, mid, u, v, info);
            if(mid < v)  search_info(id << 1 | 1, mid + 1, r, u, v, info);
        }
    }

    int find_pos(int l, int r, int kth, int target){
        vector<tuple<int, int, int>> info;
        search_info(1, 0, N - 1, l, r, info);

        for(auto [id, l, r] : info) if(mx[id] == target){
            if(kth > cnt_mx[id]){
                kth -= cnt_mx[id];
            } else return walk(id, l, r, kth);
        }
        assert(false);
        return -1;
    }
};

int N;
vector<int> H;
segment_tree_beat tr;

void initialise(int _N, int Q, int _H[]){
    N = _N;
    H.resize(N);
    for(int i = 0; i < N; ++i) H[i] = _H[i + 1];

    tr = segment_tree_beat(N);
    tr.build(1, 0, N - 1, H);
}

void cut(int l, int r, int k){
    --l, --r;
    long long tmp = tr.query(1, 0, N - 1, l, r);
//    cout << "cur : " << l << ' ' << r << ' ' << tmp << '\n';
    if(tmp <= k){
        tr.chmin(1, 0, N - 1, l, r, 0);
//        cout << '\n' << '\n';
        return;
    }

    while(true){
        int mx, mx2, cnt_mx;
        tie(mx, mx2, cnt_mx) = tr.get_info(l, r);

//        cout << mx2 << ' ' << mx << ' ' << cnt_mx << '\n';
        assert(mx2 < mx);

        long long t = 1LL * (mx - mx2) * cnt_mx;
        if(t < k){
            k -= t;
//            cout << "manual : " << l << ' ' << r << ' ' << mx2 << '\n';
            tr.chmin(1, 0, N - 1, l, r, mx2);
        } else{
            int dec = (k + cnt_mx - 1) / cnt_mx;
            int mod = k % cnt_mx;

//            cout << dec << ' ' << mod << '\n';

            if(mod > 0){
                int pos = tr.find_pos(l, r, mod, mx);
//                cout << "half : " << l << ' ' << pos << ' ' << mx - pos << '\n';
                tr.chmin(1, 0, N - 1, l, pos, mx - dec);
                assert(pos < r);
//                cout << "other  : " << pos + 1 << ' ' << r << ' ' << mx - dec + 1 << '\n';
                tr.chmin(1, 0, N -  1, pos + 1, r, mx - dec + 1);
            } else{
//                cout << "manual : " << l << ' ' << r << ' ' << mx - dec << '\n';
                tr.chmin(1, 0, N - 1, l, r, mx - dec);
            }

            break;
        }
    }

//    cout << '\n' << '\n';
}

void magic(int i, int x){
    --i;
    tr.change(1, 0, N - 1, i, x);
}

long long inspect(int l, int r){
    --l, --r;
    return tr.query(1, 0, N - 1, l, r);
}

#ifdef LOCAL
int main(){
//    ios_base::sync_with_stdio(0); cin.tie(0);

    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);

    int N, Q;
    cin >> N >> Q;
    int H[N + 1];
    for(int i = 1; i <= N; ++i) cin >> H[i];

    initialise(N, Q, H);

    while(Q--){
        int t;
        cin >> t;
        if(t == 1){
            int l, r, k;
            cin >> l >> r >> k;
            cut(l, r, k);
        } else if(t == 2){
            int i, x;
            cin >> i >> x;
            magic(i, x);
        } else{
            int l, r;
            cin >> l >> r;
            cout << inspect(l, r) << '\n';
        }
    }

    return 0;
}
#endif //LOCAL

• 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