oj.uz

Submission #541772

# Submission time Handle Problem Language Result Execution time Memory
541772 2022-03-24T11:29:58 Z eecs Weirdtree (RMI21_weirdtree) C++17
100 / 100
 998 ms 41076 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 300010;
int n, tag[maxn << 2];
bool mark[maxn << 2];
struct node { int mx, freq, sec; ll sum; } t[maxn << 2];

node operator + (node A, node B) {
    if (A.mx < B.mx) swap(A, B);
    if (A.mx > B.mx) return {A.mx, A.freq, max(A.sec, B.mx), A.sum + B.sum};
    return {A.mx, A.freq + B.freq, max(A.sec, B.sec), A.sum + B.sum};
}

node apply(node A, int k) {
    return {min(A.mx, k), A.freq, A.sec, A.sum - 1LL * A.freq * max(0, A.mx - k)};
}

#define mid ((l + r) >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
void apply(int k, int v) {
    if (mark[k]) {
        int x = min(v, t[k].mx);
        t[k] = {x, 1, (int)-1e9, x};
    } else if (v > t[k].sec && v < tag[k]) {
        t[k] = apply(t[k], tag[k] = v);
    } else if (v <= t[k].sec) {
        apply(ls, v), apply(rs, v);
        t[k] = t[ls] + t[rs], tag[k] = INT_MAX;
    }
}

void pushdown(int k) {
    apply(ls, tag[k]), apply(rs, tag[k]), tag[k] = INT_MAX;
}

void build(int k, int l, int r, int *h) {
    tag[k] = INT_MAX;
    if (l == r) { t[k] = {h[l], 1, (int)-1e9, h[l]}, mark[k] = 1; return; }
    build(ls, l, mid, h), build(rs, mid + 1, r, h);
    t[k] = t[ls] + t[rs];
}

void upd(int k, int l, int r, int p, int v) {
    if (l == r) { t[k] = {v, 1, (int)-1e9, v}; return; }
    pushdown(k);
    mid >= p ? upd(ls, l, mid, p, v) : upd(rs, mid + 1, r, p, v);
    t[k] = t[ls] + t[rs];
}

void modify(int k, int l, int r, int ql, int qr, int v) {
    if (l >= ql && r <= qr) return apply(k, v);
    pushdown(k);
    if (mid >= ql) modify(ls, l, mid, ql, qr, v);
    if (mid < qr) modify(rs, mid + 1, r, ql, qr, v);
    t[k] = t[ls] + t[rs];
}

int find(int k, int l, int r, int ql, int qr, int v1, int &v2) {
    if (t[k].mx < v1) return 0;
    if (l >= ql && r <= qr && t[k].freq < v2) return v2 -= t[k].freq, 0;
    if (l == r) return l;
    pushdown(k);
    int t = 0;
    if (mid >= ql) t = find(ls, l, mid, ql, qr, v1, v2);
    if (mid < qr && !t) t = find(rs, mid + 1, r, ql, qr, v1, v2);
    return t;
}

node query(int k, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return t[k];
    pushdown(k);
    if (mid >= qr) return query(ls, l, mid, ql, qr);
    if (mid < ql) return query(rs, mid + 1, r, ql, qr);
    return query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr);
}

void initialise(int _n, int, int *h) {
    build(1, 1, n = _n, h);
}

void cut(int l, int r, int k) {
    while (k) {
        auto p = query(1, 1, n, l, r);
        ll rem = 1LL * (p.mx - p.sec) * p.freq;
        if (rem <= k) {
            modify(1, 1, n, l, r, max(0, p.sec)), k -= rem;
        } else {
            int need = k % p.freq;
            int i = need ? find(1, 1, n, l, r, p.mx, need) : l - 1;
            if (i >= l) modify(1, 1, n, l, i, max(0, p.mx - k / p.freq - 1));
            modify(1, 1, n, i + 1, r, max(0, p.mx - k / p.freq)); break;
        }
    }
}

void magic(int i, int x) {
    upd(1, 1, n, i, x);
}

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 138 ms 8572 KB Output is correct
4 Correct 155 ms 8440 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 5 ms 460 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 998 ms 34020 KB Output is correct
4 Correct 728 ms 41076 KB Output is correct
5 Correct 946 ms 40980 KB Output is correct
6 Correct 661 ms 40780 KB Output is correct
7 Correct 11 ms 8020 KB Output is correct
8 Correct 127 ms 8076 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8020 KB Output is correct
2 Correct 127 ms 8076 KB Output is correct
3 Correct 262 ms 32580 KB Output is correct
4 Correct 344 ms 32592 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 138 ms 8572 KB Output is correct
4 Correct 155 ms 8440 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 11 ms 8020 KB Output is correct
8 Correct 127 ms 8076 KB Output is correct
9 Correct 115 ms 8440 KB Output is correct
10 Correct 139 ms 8500 KB Output is correct
11 Correct 127 ms 8400 KB Output is correct
12 Correct 171 ms 8640 KB Output is correct
13 Correct 118 ms 8456 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 138 ms 8572 KB Output is correct
4 Correct 155 ms 8440 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 998 ms 34020 KB Output is correct
8 Correct 728 ms 41076 KB Output is correct
9 Correct 946 ms 40980 KB Output is correct
10 Correct 661 ms 40780 KB Output is correct
11 Correct 262 ms 32580 KB Output is correct
12 Correct 344 ms 32592 KB Output is correct
13 Correct 115 ms 8440 KB Output is correct
14 Correct 139 ms 8500 KB Output is correct
15 Correct 127 ms 8400 KB Output is correct
16 Correct 171 ms 8640 KB Output is correct
17 Correct 118 ms 8456 KB Output is correct
18 Correct 11 ms 8020 KB Output is correct
19 Correct 127 ms 8076 KB Output is correct
20 Correct 543 ms 40100 KB Output is correct
21 Correct 724 ms 40616 KB Output is correct
22 Correct 582 ms 40364 KB Output is correct
23 Correct 696 ms 40332 KB Output is correct
24 Correct 581 ms 40176 KB Output is correct