Submission #893136

#	Time	Username	Problem	Language	Result	Execution time	Memory
893136		fanwen	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	1561 ms	12864 KiB

weirdtree

#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
 
const int MAX = 3e5 + 5;
const int BLOCK = sqrt(MAX);
const int INF = 1e9 + 1;
 
struct node {
    long long sum;
    int ma1, ma2, fr, lazy;
    node(long long sum = 0, int ma1 = 0, int ma2 = 0, int fr = 0, int lazy = INF) : sum(sum), ma1(ma1), ma2(ma2), fr(fr), lazy(lazy) {}
} infor[600 + 5] ;
 
int n, h[MAX];
 
int id_block(int pos) {
    return (pos) / BLOCK;
}
 
int begin_block(int id) {
    return id * BLOCK;
}
 
int end_block(int id) {
    return min((id + 1) * BLOCK, n) - 1;
}
 
void build_block(int id) {
    int l = begin_block(id), r = end_block(id);
    infor[id].ma1 = infor[id].ma2 = infor[id].fr = infor[id].sum = 0;
    for (int i = l; i <= r; ++i) {
        h[i] = min(h[i], infor[id].lazy);
        infor[id].sum += h[i];
        if(infor[id].ma1 < h[i]) {
            infor[id].ma2 = infor[id].ma1;
            infor[id].ma1 = h[i];
            infor[id].fr = 1;
        } else {
            if(h[i] == infor[id].ma1) infor[id].fr++;
            else infor[id].ma2 = max(infor[id].ma2, h[i]);
        }
    }
    infor[id].lazy = INF;
}
 
void initialise(int _n, int q, int _h[]) {
    n = _n;
    for (int i = 0; i < n; ++i) h[i] = _h[i + 1];
    for (int i = 0; i < n; i += BLOCK) {
        build_block(i / BLOCK);
    }
}
 
node get(int l, int r) {
    node res;

    for (int i = l; i <= min(r, end_block(id_block(l))); ++i) {
        h[i] = min(h[i], infor[id_block(l)].lazy);
        if(res.ma1 < h[i]) {
            res.ma2 = res.ma1;
            res.ma1 = h[i];
            res.fr = 1;
        } else {
            if(res.ma1 == h[i]) res.fr++;
            else res.ma2 = max(res.ma2, h[i]);
        }
        res.sum += h[i];
    }
 
    if(id_block(l) != id_block(r)) {
        for (int i = begin_block(id_block(r)); i <= r; ++i) {
            h[i] = min(h[i], infor[id_block(r)].lazy);
            if(res.ma1 < h[i]) {
                res.ma2 = res.ma1;
                res.ma1 = h[i];
                res.fr = 1;
            } else {
                if(res.ma1 == h[i]) res.fr++;
                else res.ma2 = max(res.ma2, h[i]);
            }
            res.sum += h[i];
        }
    }
 
    for (int i = id_block(l) + 1; i < id_block(r); ++i) {
        if(res.ma1 < infor[i].ma1) {
            res.ma2 = res.ma1;
            res.ma1 = infor[i].ma1;
            res.fr = infor[i].fr;
        } else {
            if(res.ma1 == infor[i].ma1) res.fr += infor[i].fr;
            else res.ma2 = max(res.ma2, infor[i].ma1);
        }
        res.sum += infor[i].sum;
        if(res.ma2 < infor[i].ma2) res.ma2 = infor[i].ma2;
    }
    return res;
}
 
void cut(int l, int r, int k) {
    l--, r--;
    while(k > 0) {
        node res = get(l, r);
        if(res.ma1 == 0) break;
        long long tmp = 1LL * res.fr * (res.ma1 - res.ma2);
        if(k >= tmp) {
            k -= tmp;
            for (int i = l; i <= min(r, end_block(id_block(l))); ++i) {
                h[i] = min(h[i], res.ma2);
            }
            build_block(id_block(l));
 
            if(id_block(l) != id_block(r)) {
                for (int i = begin_block(id_block(r)); i <= r; ++i) {
                    h[i] = min(h[i], res.ma2);
                }
                build_block(id_block(r));
            }
 
            for (int i = id_block(l) + 1; i < id_block(r); ++i) {
                if(infor[i].ma1 == res.ma1) {
                    infor[i].lazy = res.ma2;
                    infor[i].ma1 = res.ma2;
                    infor[i].sum -= 1LL * infor[i].fr * (res.ma1 - res.ma2);
                }
 
                if(infor[i].ma1 == infor[i].ma2) build_block(i);
            }
        } else {
            int rem = k / res.fr;
            for (int i = l; i <= min(r, end_block(id_block(l))); ++i) {
                if(h[i] == res.ma1) h[i] -= rem;
            }

            build_block(id_block(l));
            for (int i = id_block(l) + 1; i < id_block(r); ++i) {
                if(infor[i].ma1 == res.ma1) {
                    infor[i].ma1 -= rem;
                    infor[i].lazy = infor[i].ma1;
                    infor[i].sum -= 1LL * infor[i].fr * rem;
                }
            }
            if(id_block(l) != id_block(r)) {
                for (int i = begin_block(id_block(r)); i <= r; ++i) {
                    if(h[i] == res.ma1) h[i] -= rem;
                }
                build_block(id_block(r));
            }
            k = k - res.fr * rem;
            res.ma1 -= rem;
            assert(k < res.fr);
            for (int i = l; i <= end_block(id_block(l)) && k > 0; ++i) {
                if(h[i] == res.ma1) {
                    h[i]--;
                    k--;
                }
            } 
            build_block(id_block(l));
            for (int i = id_block(l) + 1; i < id_block(r) && k > 0; ++i) {
                if(infor[i].ma1 != res.ma1) continue;
                if(infor[i].fr <= k) {
                    k -= infor[i].fr;
                    infor[i].lazy = --infor[i].ma1;
                    infor[i].sum -= infor[i].fr;    
                    if(infor[i].ma1 == infor[i].ma2) build_block(i);
                } else {
                    for (int j = begin_block(i); j <= end_block(i) && k > 0; ++j) {
                        h[j] = min(h[j], infor[i].lazy);
                        if(h[j] == res.ma1) h[j]--, k--;
                    }
                    build_block(i);
                    break;
                }
            }

            if(id_block(l) != id_block(r)) {
                for (int i = begin_block(id_block(r)); i <= r && k > 0; ++i) {
                    if(h[i] == res.ma1) h[i]--, k--;
                }
                build_block(id_block(r));
            }
            assert(k <= 0);
        }
    }
}
 
void magic(int i, int x) {
    i--;
    build_block(id_block(i));
    h[i] = x;
    build_block(id_block(i));
}
 
long long inspect(int l, int r) {
    return get(l - 1, r - 1).sum;
}
 
#ifdef LOCAL
 
#include <iostream>
 
using namespace std;
 
int main() {
    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);
 
    for (int i = 1; i <= Q; ++i) {
        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
 
// Dream it. Wish it. Do it.

• 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