Submission #893008

#	Time	Username	Problem	Language	Result	Execution time	Memory
893008		fanwen	Weirdtree (RMI21_weirdtree)	C++17	Compilation error	0 ms	0 KiB

weirdtree

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

using namespace std;

#define fi first
#define se second

const int MAX = 2e5 + 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[BLOCk + 5] ;

int n, h[MAX];

int id_block(int pos) {
    return (pos - 1) / 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++;
            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) {
        if(res.ma1 < h[i]) {
            res.ma2 = res.ma1;
            res.ma1 = h[i];
            res.fr = 1;
        } else {
            if(res.ma1 == h[i]) res.fr++;
            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) {
            if(res.ma1 < h[i]) {
                res.ma2 = res.ma1;
                res.ma1 = h[i];
                res.fr = 1;
            } else {
                if(res.ma1 == h[i]) res.fr++;
                res.ma2 = max(res.ma2, h[i]);
            }
            res.sum += h[i];
        }
    }

    for (int i = id_block(l); ++i < id_block(r);) {
        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;
            res.ma2 = max(res.ma2, infor[i].ma1);
        }
        res.sum += infor[i].sum;
    }
    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); ++i < id_block(r);) {
                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 tmp =
            k = 0;
            for (int i = l; i <= min(r, end_block(id_block(l))); ++i) {

            }
        }
    }
}

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() {
    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.

Compilation message (stderr)

weirdtree.cpp:17:9: error: 'BLOCk' was not declared in this scope; did you mean 'BLOCK'?
   17 | } infor[BLOCk + 5] ;
      |         ^~~~~
      |         BLOCK
weirdtree.cpp: In function 'void build_block(int)':
weirdtree.cpp:35:5: error: 'infor' was not declared in this scope
   35 |     infor[id].ma1 = infor[id].ma2 = infor[id].fr = infor[id].sum = 0;
      |     ^~~~~
weirdtree.cpp: In function 'node get(int, int)':
weirdtree.cpp:88:22: error: 'infor' was not declared in this scope
   88 |         if(res.ma1 < infor[i].ma1) {
      |                      ^~~~~
weirdtree.cpp:96:20: error: 'infor' was not declared in this scope
   96 |         res.sum += infor[i].sum;
      |                    ^~~~~
weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:122:20: error: 'infor' was not declared in this scope
  122 |                 if(infor[i].ma1 == res.ma1) {
      |                    ^~~~~
weirdtree.cpp:128:20: error: 'infor' was not declared in this scope
  128 |                 if(infor[i].ma1 == infor[i].ma2) build_block(i);
      |                    ^~~~~
weirdtree.cpp:131:17: warning: unused variable 'tmp' [-Wunused-variable]
  131 |             int tmp =
      |                 ^~~