oj.uz

Submission #541771

# Submission time Handle Problem Language Result Execution time Memory
541771 2022-03-24T11:25:35 Z eecs Weirdtree (RMI21_weirdtree) C++17
52 / 100
 2000 ms 39984 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];
}

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 i = l - 1;
            if (k % p.freq) {
                int lb = l, rb = r;
                while (lb <= rb) {
                    int m = (lb + rb) / 2;
                    auto q = query(1, 1, n, l, m);
                    if (p.mx == q.mx && q.freq >= k % p.freq) rb = (i = m) - 1;
                    else lb = m + 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 468 KB Output is correct
2 Correct 1 ms 356 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 124 ms 10436 KB Output is correct
4 Correct 320 ms 10484 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Execution timed out 2063 ms 39984 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 36828 KB Output is correct
2 Correct 1022 ms 39776 KB Output is correct
3 Correct 12 ms 10188 KB Output is correct
4 Correct 381 ms 9876 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 124 ms 10436 KB Output is correct
4 Correct 320 ms 10484 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 12 ms 10188 KB Output is correct
8 Correct 381 ms 9876 KB Output is correct
9 Correct 117 ms 10444 KB Output is correct
10 Correct 321 ms 10476 KB Output is correct
11 Correct 115 ms 10388 KB Output is correct
12 Correct 317 ms 10512 KB Output is correct
13 Correct 140 ms 10540 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 124 ms 10436 KB Output is correct
4 Correct 320 ms 10484 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Execution timed out 2063 ms 39984 KB Time limit exceeded
8 Halted 0 ms 0 KB -