Submission #1126786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126786		_callmelucian	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	679 ms	50908 KiB

weirdtree

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 3e5 + 5;

struct ITBeats {
private:
    vector<ll> sum, hi, secHi, cntHi, lazy;

public:
    ITBeats (int sz) : sum(4 * sz), hi(4 * sz), secHi(4 * sz, LLONG_MIN),
                       cntHi(4 * sz, 1), lazy(4 * sz, LLONG_MIN) {}

private:
    void apply (int k, int chmin) {
//        cout << "apply " << hi[k] << " " << chmin << "\n";
        sum[k] -= (hi[k] - chmin) * cntHi[k];
        lazy[k] = hi[k] = chmin;
        assert(hi[k] != secHi[k]);
    }

    void refine (int k) {
        sum[k] = sum[k << 1] + sum[k << 1 | 1];
        if (hi[k << 1] == hi[k << 1 | 1]) {
            hi[k] = hi[k << 1], secHi[k] = max(secHi[k << 1], secHi[k << 1 | 1]);
            cntHi[k] = cntHi[k << 1] + cntHi[k << 1 | 1];
        }
        else if (hi[k << 1] > hi[k << 1 | 1]) {
            hi[k] = hi[k << 1], cntHi[k] = cntHi[k << 1];
            secHi[k] = max(secHi[k << 1], hi[k << 1 | 1]);
        }
        else {
            hi[k] = hi[k << 1 | 1], cntHi[k] = cntHi[k << 1 | 1];
            secHi[k] = max(hi[k << 1], secHi[k << 1 | 1]);
        }
        assert(hi[k] > secHi[k]);
    }

    void pushDown (int k, int l, int r) {
        if (lazy[k] == LLONG_MIN) return;
//        int mid = (l + r) >> 1;
//        update(l, mid, lazy[k], k << 1, l, mid);
//        update(mid + 1, r, lazy[k], k << 1 | 1, mid + 1, r);
        if (lazy[k] < hi[k << 1]) apply(k << 1, lazy[k]);
        if (lazy[k] < hi[k << 1 | 1]) apply(k << 1 | 1, lazy[k]);
        lazy[k] = LLONG_MIN;
    }

    pl merging (pl a, pl b) {
        if (a.first == b.first) return {a.first, max(a.second, b.second)};
        if (a.first > b.first) return {a.first, max(a.second, b.first)};
        if (a.first < b.first) return {b.first, max(a.first, b.second)};
    }

public:
    void update (int a, int b, int chmin, int k = 1, int l = 1, int r = mn) {
        if (b < l || r < a || chmin >= hi[k]) return;
        if (a <= l && r <= b) {
            if (secHi[k] < chmin && chmin < hi[k])
                return apply(k, chmin), void();
        }
        pushDown(k, l, r);
        int mid = (l + r) >> 1;
        update(a, b, chmin, k << 1, l, mid);
        update(a, b, chmin, k << 1 | 1, mid + 1, r);
        refine(k);
    }

    void assgn (int pos, int val, int k = 1, int l = 1, int r = mn) {
        if (pos < l || r < pos) return;
        if (l == r)
            return hi[k] = sum[k] = val, secHi[k] = LLONG_MIN, cntHi[k] = 1, void();
        pushDown(k, l, r); int mid = (l + r) >> 1;
        assgn(pos, val, k << 1, l, mid);
        assgn(pos, val, k << 1 | 1, mid + 1, r);
        refine(k);
    }

    ll query (int a, int b, int k = 1, int l = 1, int r = mn) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return sum[k];
        pushDown(k, l, r); int mid = (l + r) >> 1;
        return query(a, b, k << 1, l, mid) + query(a, b, k << 1 | 1, mid + 1, r);
    }

    int queryCnt (int a, int b, int hiCur, int k = 1, int l = 1, int r = mn) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return (hi[k] == hiCur ? cntHi[k] : 0);
        pushDown(k, l, r); int mid = (l + r) >> 1;
        return queryCnt(a, b, hiCur, k << 1, l, mid) +
               queryCnt(a, b, hiCur, k << 1 | 1, mid + 1, r);
    }

    pl queryMax (int a, int b, int k = 1, int l = 1, int r = mn) {
        if (b < l || r < a) return make_pair(LLONG_MIN, LLONG_MIN);
        if (a <= l && r <= b) {
            assert(hi[k] > secHi[k]);
//            cout << "g(" << hi[k] << ") ";
            return make_pair(hi[k], secHi[k]);
        }
        pushDown(k, l, r); int mid = (l + r) >> 1;
        return merging(queryMax(a, b, k << 1, l, mid),
                       queryMax(a, b, k << 1 | 1, mid + 1, r));
    }

    int walking (int need, int hiCur, int k, int l, int r) {
        if (l == r) {
            int cntCur = (hi[k] == hiCur ? cntHi[k] : 0);
            return (cntCur ? l : l - 1);
        }
        pushDown(k, l, r); int mid = (l + r) >> 1;
        int cntLeft = (hi[k << 1] == hiCur ? cntHi[k << 1] : 0);
        if (cntLeft >= need) return walking(need, hiCur, k << 1, l, mid);
        return walking(need - cntLeft, hiCur, k << 1 | 1, mid + 1, r);
    }

    int walk (int a, int b, int need, int hiCur, int k = 1, int l = 1, int r = mn) {
//        cout << "walk " << a << ".." << b << " " << need << " " << hiCur << " " << l << ".." << r << " " << hi[k] << "\n";
        if (b < l || r < a) return r;
        if (a <= l && r <= b) {
            int curCnt = (hi[k] == hiCur ? cntHi[k] : 0);
            return (curCnt >= need ? walking(need, hiCur, k, l, r) : r);
        }
        pushDown(k, l, r);
        int mid = (l + r) >> 1, goLeft = walk(a, b, need, hiCur, k << 1, l, mid);
        int cntLeft = queryCnt(a, b, hiCur, k << 1, l, mid);
        return (goLeft == mid && mid < b && cntLeft < need ? walk(a, b, need - cntLeft, hiCur, k << 1 | 1, mid + 1, r) : goLeft);
    }
} tree(mn);

void initialise (int _N, int _Q, int h[]) {
    for (int i = 1; i <= _N; i++) tree.assgn(i, h[i]);
}

void cut (int l, int r, int k) {
    int oldK = k;
    while (k > 0) {
        ll best, secBest; tie(best, secBest) = tree.queryMax(l, r);
        secBest = max(0LL, secBest);
        int cntHi = tree.queryCnt(l, r, best);
        if (best == 0) return;

//        cout << "pre-info " << l << ".." << r << " " << best << " " << secBest << " " << cntHi << " " << k << "\n";

        if ((best - secBest) * cntHi <= k) {
            k -= (best - secBest) * cntHi;
            tree.update(l, r, secBest);

//            cout << k - (best - secBest) * cntHi << "\n";
//            cout << "change-a " << l << ".." << r << " " << best << " -> " << secBest << "\n";
        }
        else {
            ll fully = k / cntHi, cur = best - fully;
            k -= fully * cntHi, tree.update(l, r, cur);
//            cout << "change-b " << l << ".." << r << " " << best << " -> " << cur << "\n";

            if (k) {
//                int need = tree.queryCnt(1, l - 1, cur) + k, pos = l - 1;
//                for (int step = (r - l + 1); step > 0; step >>= 1) {
//                    while (pos + step <= r && tree.queryCnt(l, pos + step, cur) < k) pos += step;
//                }
//                pos++;
                int pos = tree.walk(l, r, k, cur);
                tree.update(l, min(pos, r), cur - 1), k = 0;
//                cout << "change-c " << need << " " << l << ".." << pos << " " << cur << " -> " << cur - 1 << "\n";
            }
        }
//        if (oldK == k) {
//            cout << "f " << oldK << " " << k << "\n";
//            exit(0);
//        }
//        oldK = k;
    }
}

void magic (int i, int x) {
    tree.assgn(i, x);
}

ll inspect (int l, int r) {
    return tree.query(l, r, 1);
}

#ifdef LOCAL
int init[mn];

int main()
{
    freopen("WEIRD.inp", "r", stdin);
    freopen("WEIRD.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> init[i];

    initialise(n, q, init);
    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int l, r, k; cin >> l >> r >> k;
            cut(l, r, k);
        }
        else if (type == 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

Compilation message (stderr)

weirdtree.cpp: In member function 'pl ITBeats::merging(pl, pl)':
weirdtree.cpp:63:5: warning: control reaches end of non-void function [-Wreturn-type]
   63 |     }
      |     ^

• 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