Submission #788636

#	Time	Username	Problem	Language	Result	Execution time	Memory
788636		79brue	Weirdtree (RMI21_weirdtree)	C++17	23 / 100	114 ms	53424 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    struct Node{
        ll max1, max2, maxCnt, sum, lazy;
        Node(){}
        Node(ll max1, ll max2, ll maxCnt, ll sum, ll lazy): max1(max1), max2(max2), maxCnt(maxCnt), sum(sum), lazy(lazy){}
    } tree[1<<20];


    void merge(int i){
        tree[i].max1 = max(tree[i*2].max1, tree[i*2+1].max1);
        tree[i].max2 = max(tree[i*2].max1 == tree[i].max1 ? tree[i*2].max2 : tree[i*2].max1,
                           tree[i*2+1].max1 == tree[i].max1 ? tree[i*2+1].max2 : tree[i*2+1].max1);
        tree[i].maxCnt = (tree[i*2].max1 == tree[i].max1 ? tree[i*2].maxCnt : 0) +
                         (tree[i*2+1].max1 == tree[i].max1 ? tree[i*2+1].maxCnt : 0);
        tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
    }

    Node merge(Node a, Node b){
        return Node(max(a.max1, b.max1),
                    max(a.max1 >= b.max1 ? a.max2 : a.max1, b.max1 >= a.max1 ? b.max2 : b.max1),
                    (a.max1 >= b.max1 ? a.maxCnt : 0) + (b.max1 >= a.max1 ? b.maxCnt : 0), a.sum + b.sum, 0);
    }

    void init(int i, int l, int r, ll *A){
        tree[i].lazy = INT_MAX;
        if(l==r){
            tree[i].max1 = A[l], tree[i].max2 = -1, tree[i].maxCnt = 1, tree[i].sum = A[l];
            tree[i].lazy = INT_MAX;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        merge(i);
    }

    void propagate(int i, int l, int r){
        if(tree[i].lazy == INT_MAX) return;
        tree[i].sum -= (tree[i].max1 - tree[i].lazy) * tree[i].maxCnt;
        tree[i].max1 = tree[i].lazy;
        if(l!=r){
            if(tree[i*2].max1 > tree[i].lazy) tree[i*2].lazy = min(tree[i*2].lazy, tree[i].lazy);
            if(tree[i*2+1].max1 > tree[i].lazy) tree[i*2+1].lazy = min(tree[i*2+1].lazy, tree[i].lazy);
        }
        tree[i].lazy = INT_MAX;
    }

    void cut(int i, int l, int r, int s, int e, ll v){
        propagate(i, l, r);
        if(r<s || e<l || tree[i].max1 <= v) return;
        if(s<=l && r<=e && tree[i].max2 < v){
            tree[i].lazy = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        cut(i*2, l, m, s, e, v);
        cut(i*2+1, m+1, r, s, e, v);
        merge(i);
    }

    int cutK(int i, int l, int r, int s, int e, ll v, ll k){
        propagate(i, l, r);
        if(r<s || e<l || !k || tree[i].max1 <= v) return 0;
        if(s<=l && r<=e && tree[i].max2 < v && tree[i].maxCnt <= k){
            ll tmp = tree[i].maxCnt;
            tree[i].lazy = v;
            propagate(i, l, r);
            return tmp;
        }
        int m = (l+r)>>1;
        ll tmp = 0;
        tmp += cutK(i*2, l, m, s, e, v, k);
        if(k-tmp) tmp += cutK(i*2+1, m+1, r, s, e, v, k-tmp);
        merge(i);
        return tmp;
    }

    Node query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return Node(-1, -1, 0, 0, INT_MAX);
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return merge(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }

    void updateSingle(int i, int l, int r, int x, ll v){
        propagate(i, l, r);
        if(l==r){
            tree[i] = Node(v, -1, 1, v, INT_MAX);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) updateSingle(i*2, l, m, x, v), propagate(i*2+1, m+1, r);
        else     updateSingle(i*2+1, m+1, r, x, v), propagate(i*2, l, m);
        merge(i);
    }
} tree;

int n, q;
ll arr[300002];

void initialise(int N, int Q, int h[]) {
	n = N, q = Q;
	for(int i=1; i<=n; i++) arr[i] = h[i];
	tree.init(1, 1, n, arr);
}

void cut(int l, int r, int k){
	while(k){
        segTree::Node tmp = tree.query(1, 1, n, l, r);
        ll mx = tmp.max1, to = max(tmp.max2, 0LL), cnt = tmp.maxCnt;
        if(mx == 0) break;
        else if((mx-to)*cnt <= k){
            k -= (mx-to)*cnt;
            tree.cut(1, 1, n, l, r, to);
        }
        else{
            ll to2 = mx - k/cnt;
            if(to2 != mx) tree.cut(1, 1, n, l, r, to2);
            if(k%cnt) tree.cutK(1, 1, n, l, r, to2-1, k);
            break;
        }
	}
}

void magic(int i, int x) {
	tree.updateSingle(1, 1, n, i, x);
}

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

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