oj.uz

답안 #498662

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498662 2021-12-26T04:45:38 Z model_code Weirdtree (RMI21_weirdtree) C++17
100 / 100
 1150 ms 39580 KB 
// weirdtree_100_tamio.cpp

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

constexpr int inf = 1e9 + 100, maxn = 1 << 20;

struct element {
    long long sum;
    int max, max2, nr;
};

element mk_element(int x) { return element{x, x, -inf, 1}; }

constexpr element zero{0, -inf, -inf, 0};

element operator+(element a, element b) {
    return a.max == b.max
               ? element{a.sum + b.sum, a.max, max(a.max2, b.max2), a.nr + b.nr}
           : a.max > b.max
               ? element{a.sum + b.sum, a.max, max(a.max2, b.max), a.nr}
               : element{a.sum + b.sum, b.max, max(a.max, b.max2), b.nr};
}

element operator*(int x, element a) {
    assert(x > a.max2);
    return element{a.sum - (long long)a.nr * max(a.max - x, 0), min(a.max, x),
                   a.max2, a.nr};
}

int lazy[maxn];
element buf[2 * maxn];

void apply(int i, int x) {
    if (i >= maxn)
        buf[i] = mk_element(min(buf[i].max, x));
    else if (x > buf[i].max2 && x < lazy[i]) {
        lazy[i] = x;
        buf[i] = x * buf[i];
    } else if (x <= buf[i].max2) {
        apply(2 * i, x);
        apply(2 * i + 1, x);
        lazy[i] = inf;
        buf[i] = buf[2 * i] + buf[2 * i + 1];
    }
}

void prop(int i) {
    if (i < maxn) {
        apply(2 * i, lazy[i]);
        apply(2 * i + 1, lazy[i]);
        lazy[i] = inf;
    }
}

void up(int x) {
    while (x /= 2) buf[x] = lazy[x] * (buf[2 * x] + buf[2 * x + 1]);
}

void down(int x) {
    for (int i = __builtin_ctz(maxn); i > 0; --i)
        if (x >> i) prop(x >> i);
}

element query(int st, int dr) {
    down(st += maxn);
    down((dr += maxn) - 1);

    element ret = zero;
    for (; st < dr; st /= 2, dr /= 2) {
        if (st % 2) ret = ret + buf[st++];
        if (dr % 2) ret = ret + buf[--dr];
    }

    return ret;
}

void update(int st, int dr, int x) {
    down(st += maxn);  // astea probabil pot fi sterse, vreau sa vad.
    down((dr += maxn) - 1);

    const int st0 = st, dr0 = dr;
    for (; st < dr; st /= 2, dr /= 2) {
        if (st % 2) apply(st++, x);
        if (dr % 2) apply(--dr, x);
    }

    up(st0);
    up(dr0 - 1);
}

int cbin(int st, int dr, int k) {
    auto t = query(st, dr);
    int k_ = t.nr - k, x = -1;

    auto upd = [&](int& k, int& k_, int i) {
        if (buf[i].max < t.max) return;
        if (k <= buf[i].nr) {
            x = i;
            k_ = buf[i].nr - k;
        } else
            k -= buf[i].nr;
    };

    for (st += maxn, dr += maxn; st < dr && x == -1; st /= 2, dr /= 2) {
        if (st % 2) upd(k, k_, st++);
        if (x == -1 && dr % 2) upd(k_, k, --dr);
    }

    while (x < maxn) {
        prop(x);
        x *= 2;
        if (buf[x].max < t.max)
            ++x;
        else if (buf[x].nr <= k)
            k -= buf[x++].nr;
    }

    if (k) ++x;

    return x - maxn;
}

void initialise(int n, int q, int h[]) {
    for (int i = 0; i < n; ++i) buf[i + maxn] = mk_element(h[i + 1]);
    for (int i = maxn - 1; i > 0; --i) {
        buf[i] = buf[2 * i] + buf[2 * i + 1];
        lazy[i] = inf;
    }
}

void cut(int l, int r, int k) {
    --l;
    while (k) {
        auto t = query(l, r);
        long long ops = (long long)(t.max - t.max2) * t.nr;
        if (ops <= k) {
            k -= ops;
            update(l, r, max(t.max2, 0));
        } else {
            int i = cbin(l, r, k % t.nr);
            update(l, i, max(t.max - k / t.nr - 1, 0));
            update(i, r, max(t.max - k / t.nr, 0));
            k = 0;
        }
    }
}

void magic(int i, int x) {
    down(i += maxn - 1);
    buf[i] = mk_element(x);
    up(i);
}

long long inspect(int l, int r) {
    auto t = query(l - 1, r);
    return t.sum;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 29132 KB Output is correct
2 Correct 21 ms 29132 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 29132 KB Output is correct
2 Correct 21 ms 29132 KB Output is correct
3 Correct 203 ms 31668 KB Output is correct
4 Correct 174 ms 31572 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 29092 KB Output is correct
2 Correct 24 ms 29132 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 29092 KB Output is correct
2 Correct 24 ms 29132 KB Output is correct
3 Correct 1150 ms 39492 KB Output is correct
4 Correct 929 ms 39580 KB Output is correct
5 Correct 1027 ms 39320 KB Output is correct
6 Correct 927 ms 39112 KB Output is correct
7 Correct 233 ms 31320 KB Output is correct
8 Correct 267 ms 31320 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 31320 KB Output is correct
2 Correct 267 ms 31320 KB Output is correct
3 Correct 465 ms 38408 KB Output is correct
4 Correct 663 ms 38860 KB Output is correct

Subtask #6
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 29132 KB Output is correct
2 Correct 21 ms 29132 KB Output is correct
3 Correct 203 ms 31668 KB Output is correct
4 Correct 174 ms 31572 KB Output is correct
5 Correct 24 ms 29092 KB Output is correct
6 Correct 24 ms 29132 KB Output is correct
7 Correct 233 ms 31320 KB Output is correct
8 Correct 267 ms 31320 KB Output is correct
9 Correct 192 ms 31656 KB Output is correct
10 Correct 178 ms 31596 KB Output is correct
11 Correct 218 ms 31588 KB Output is correct
12 Correct 200 ms 31716 KB Output is correct
13 Correct 182 ms 31740 KB Output is correct

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 29132 KB Output is correct
2 Correct 21 ms 29132 KB Output is correct
3 Correct 203 ms 31668 KB Output is correct
4 Correct 174 ms 31572 KB Output is correct
5 Correct 24 ms 29092 KB Output is correct
6 Correct 24 ms 29132 KB Output is correct
7 Correct 1150 ms 39492 KB Output is correct
8 Correct 929 ms 39580 KB Output is correct
9 Correct 1027 ms 39320 KB Output is correct
10 Correct 927 ms 39112 KB Output is correct
11 Correct 465 ms 38408 KB Output is correct
12 Correct 663 ms 38860 KB Output is correct
13 Correct 192 ms 31656 KB Output is correct
14 Correct 178 ms 31596 KB Output is correct
15 Correct 218 ms 31588 KB Output is correct
16 Correct 200 ms 31716 KB Output is correct
17 Correct 182 ms 31740 KB Output is correct
18 Correct 233 ms 31320 KB Output is correct
19 Correct 267 ms 31320 KB Output is correct
20 Correct 736 ms 38076 KB Output is correct
21 Correct 918 ms 38908 KB Output is correct
22 Correct 935 ms 38548 KB Output is correct
23 Correct 877 ms 38632 KB Output is correct
24 Correct 862 ms 38468 KB Output is correct