oj.uz

Submission #590117

# Submission time Handle Problem Language Result Execution time Memory
590117 2022-07-05T14:33:32 Z davi_bart Weirdtree (RMI21_weirdtree) C++14
100 / 100
 1196 ms 52592 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

#include "weirdtree.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define int ll
using namespace std;
struct segtree_beats {
    struct node {
        int ma1, ma2, freq;
        int sum, abbassa;
        node(int a = -1, int b = -1, int c = 1, int d = 0, int e = -1) {
            ma1 = a;
            ma2 = b;
            freq = c;
            sum = d;
            abbassa = e;
        }
    };
    static const int dim = 1 << 19;
    vector<node> s = vector<node>(2 * dim);
    void sist(int pos, int l, int r) {
        if (s[pos].abbassa == -1) return;
        if (s[pos].ma1 <= s[pos].abbassa) {
            s[pos].abbassa = -1;
            return;
        }
        s[pos].sum -= (s[pos].ma1 - s[pos].abbassa) * s[pos].freq;
        s[pos].ma1 = s[pos].abbassa;
        if (pos < dim) {
            if (s[2 * pos].abbassa == -1 || s[2 * pos].abbassa > s[pos].abbassa) s[2 * pos].abbassa = s[pos].abbassa;
            if (s[2 * pos + 1].abbassa == -1 || s[2 * pos + 1].abbassa > s[pos].abbassa) s[2 * pos + 1].abbassa = s[pos].abbassa;
        }
        s[pos].abbassa = -1;
    }
    void recalc(int pos) {
        if (s[2 * pos].ma1 > s[2 * pos + 1].ma1) {
            s[pos].ma1 = s[2 * pos].ma1;
            s[pos].freq = s[2 * pos].freq;
            s[pos].ma2 = max(s[2 * pos].ma2, s[2 * pos + 1].ma1);
        } else if (s[2 * pos].ma1 < s[2 * pos + 1].ma1) {
            s[pos].ma1 = s[2 * pos + 1].ma1;
            s[pos].freq = s[2 * pos + 1].freq;
            s[pos].ma2 = max(s[2 * pos].ma1, s[2 * pos + 1].ma2);
        } else {
            s[pos].ma1 = s[2 * pos].ma1;
            s[pos].freq = s[2 * pos].freq + s[2 * pos + 1].freq;
            s[pos].ma2 = max(s[2 * pos].ma2, s[2 * pos + 1].ma2);
        }
        s[pos].sum = s[2 * pos].sum + s[2 * pos + 1].sum;
    }
    void setta(int pos, int l, int r, int p, int val) {
        sist(pos, l, r);
        if (p < l || r < p) return;
        if (l == r) {
            s[pos] = {val, -1, 1, val, -1};
            return;
        }
        int m = (l + r) / 2;
        setta(2 * pos, l, m, p, val);
        setta(2 * pos + 1, m + 1, r, p, val);
        recalc(pos);
    }
    void setta(int p, int val) { setta(1, 0, dim - 1, p, val); }

    int abbassa(int pos, int l, int r, int a, int b, int k, bool apply, int count) {
        sist(pos, l, r);
        if (b < l || r < a) return 0;
        if (s[pos].ma1 <= k) return 0;
        if (a <= l && r <= b && s[pos].ma2 < k) {
            int tot = (s[pos].ma1 - k) * s[pos].freq;
            if (apply) {
                s[pos].abbassa = k;
                sist(pos, l, r);
            }
            return tot;
        }
        int m = (l + r) / 2;
        int tot = abbassa(2 * pos, l, m, a, b, k, apply, count);
        count -= tot;
        if (count > 0) {
            tot += abbassa(2 * pos + 1, m + 1, r, a, b, k, apply, count);
        } else {
            sist(2 * pos + 1, m + 1, r);
        }
        recalc(pos);
        return tot;
    }
    int abbassa(int a, int b, int k, bool apply, int count) { return abbassa(1, 0, dim - 1, a, b, k, apply, count); }

    int abbassa1(int pos, int l, int r, int a, int b, int k, int count) {
        sist(pos, l, r);
        if (count == 0) return 0;
        if (b < l || r < a) return 0;
        if (s[pos].ma1 <= k) return 0;
        if (a <= l && r <= b && s[pos].ma2 < k && (s[pos].ma1 - k) * s[pos].freq <= count) {
            int tot = (s[pos].ma1 - k) * s[pos].freq;
            s[pos].abbassa = k;
            sist(pos, l, r);
            return tot;
        }
        int m = (l + r) / 2;
        int tot = abbassa1(2 * pos, l, m, a, b, k, count);
        count -= tot;
        tot += abbassa1(2 * pos + 1, m + 1, r, a, b, k, count);
        recalc(pos);
        return tot;
    }
    int abbassa1(int a, int b, int k, int count) { return abbassa1(1, 0, dim - 1, a, b, k, count); }

    int query(int pos, int l, int r, int a, int b) {
        sist(pos, l, r);
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return s[pos].sum;
        int m = (l + r) / 2;
        int tot = query(2 * pos, l, m, a, b) + query(2 * pos + 1, m + 1, r, a, b);
        // recalc(pos);
        return tot;
    }
    int query(int a, int b) { return query(1, 0, dim - 1, a, b); }

} seg;
int N;
void dbg() {
    // for (int i = 0; i < N; i++) cout << seg.query(i, i) << " ";
    // cout << endl;
}
void initialise(signed n, signed Q, signed h[]) {
    N = n;
    for (int i = 0; i < N; i++) {
        seg.setta(i, h[i + 1]);
    }
    dbg();
}
void cut(signed l, signed r, signed k) {
    l--;
    r--;
    int x = 0, y = 1e9 + 10;
    while (x < y) {
        int m = (x + y + 1) / 2;
        int q = seg.abbassa(l, r, m, 0, k);
        if (q < k)
            y = m - 1;
        else
            x = m;
    }
    k -= seg.abbassa(l, r, x + 1, 1, k);
    // cout << x << " " << k << endl;
    // dbg();
    seg.abbassa1(l, r, x, k);

    dbg();
}
void magic(signed i, signed x) {
    i--;
    seg.setta(i, x);
    dbg();
}
ll inspect(signed l, signed r) {
    l--;
    r--;
    return seg.query(l, r);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41428 KB Output is correct
2 Correct 19 ms 41404 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41428 KB Output is correct
2 Correct 19 ms 41404 KB Output is correct
3 Correct 173 ms 43400 KB Output is correct
4 Correct 242 ms 43760 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 41400 KB Output is correct
2 Correct 24 ms 41300 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 41400 KB Output is correct
2 Correct 24 ms 41300 KB Output is correct
3 Correct 1135 ms 51328 KB Output is correct
4 Correct 823 ms 52516 KB Output is correct
5 Correct 1196 ms 52592 KB Output is correct
6 Correct 804 ms 52392 KB Output is correct
7 Correct 92 ms 43784 KB Output is correct
8 Correct 130 ms 43528 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 43784 KB Output is correct
2 Correct 130 ms 43528 KB Output is correct
3 Correct 361 ms 45480 KB Output is correct
4 Correct 526 ms 51252 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41428 KB Output is correct
2 Correct 19 ms 41404 KB Output is correct
3 Correct 173 ms 43400 KB Output is correct
4 Correct 242 ms 43760 KB Output is correct
5 Correct 25 ms 41400 KB Output is correct
6 Correct 24 ms 41300 KB Output is correct
7 Correct 92 ms 43784 KB Output is correct
8 Correct 130 ms 43528 KB Output is correct
9 Correct 172 ms 44128 KB Output is correct
10 Correct 237 ms 44012 KB Output is correct
11 Correct 168 ms 44080 KB Output is correct
12 Correct 214 ms 44164 KB Output is correct
13 Correct 211 ms 44192 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41428 KB Output is correct
2 Correct 19 ms 41404 KB Output is correct
3 Correct 173 ms 43400 KB Output is correct
4 Correct 242 ms 43760 KB Output is correct
5 Correct 25 ms 41400 KB Output is correct
6 Correct 24 ms 41300 KB Output is correct
7 Correct 1135 ms 51328 KB Output is correct
8 Correct 823 ms 52516 KB Output is correct
9 Correct 1196 ms 52592 KB Output is correct
10 Correct 804 ms 52392 KB Output is correct
11 Correct 361 ms 45480 KB Output is correct
12 Correct 526 ms 51252 KB Output is correct
13 Correct 172 ms 44128 KB Output is correct
14 Correct 237 ms 44012 KB Output is correct
15 Correct 168 ms 44080 KB Output is correct
16 Correct 214 ms 44164 KB Output is correct
17 Correct 211 ms 44192 KB Output is correct
18 Correct 92 ms 43784 KB Output is correct
19 Correct 130 ms 43528 KB Output is correct
20 Correct 640 ms 51796 KB Output is correct
21 Correct 859 ms 52092 KB Output is correct
22 Correct 680 ms 51928 KB Output is correct
23 Correct 850 ms 51980 KB Output is correct
24 Correct 667 ms 51728 KB Output is correct