oj.uz

Submission #745007

# Submission time Handle Problem Language Result Execution time Memory
745007 2023-05-19T09:52:15 Z siewjh Weirdtree (RMI21_weirdtree) C++17
42 / 100
 114 ms 26932 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 300005;

int nums;
ll height[MAXN];

struct vals{
    ll mx1, mx2, cnt1, sum;
};
vals st[MAXN * 2];
ll lazy[MAXN * 2];

vals join(vals a, vals b){
    vals res;
    if (a.mx1 > b.mx1){
        res.mx1 = a.mx1;
        res.mx2 = max(a.mx2, b.mx1);
        res.cnt1 = a.cnt1;
    }
    else if (a.mx1 < b.mx1){
        res.mx1 = b.mx1;
        res.mx2 = max(a.mx1, b.mx2);
        res.cnt1 = b.cnt1;
    }
    else{
        res.mx1 = a.mx1;
        res.mx2 = max(a.mx2, b.mx2);
        res.cnt1 = a.cnt1 + b.cnt1;
    }
    res.sum = a.sum + b.sum;
    return res;
}

void init(int ind, int s, int e){
    lazy[ind] = -1;
    if (s == e){
        st[ind] = {height[s], -1, 1, height[s]};
        return;
    }
    int m = (s + e) >> 1;
    init(ind << 1, s, m);
    init((ind << 1) + 1, m + 1, e);
    st[ind] = join(st[ind << 1], st[(ind << 1) + 1]);
}

int finalv(int ind){
    return (lazy[ind] == -1 ? st[ind].mx1 : lazy[ind]);
}

void propo(int ind, bool leaf){
    if (lazy[ind] == -1) return;
    if (!leaf){
        if (finalv(ind << 1) == st[ind].mx1) lazy[ind << 1] = lazy[ind];
        if (finalv((ind << 1) + 1) == st[ind].mx1) lazy[(ind << 1) + 1] = lazy[ind];
    }
    st[ind].sum -= st[ind].cnt1 * (st[ind].mx1 - lazy[ind]);
    st[ind].mx1 = lazy[ind];
    lazy[ind] = -1;
}

void updatemin(int ind, int s, int e, int l, int r, ll v){
    propo(ind, s == e);
    if (v >= st[ind].mx1) return;
    if (l == s && r == e){
        if (v > st[ind].mx2){
            lazy[ind] = v;
            return;
        }
    }
    int m = (s + e) >> 1;
    if (l <= m) updatemin(ind << 1, s, m, l, min(r, m), v);
    if (r > m) updatemin((ind << 1) + 1, m + 1, e, max(l, m + 1), r, v);
    propo(ind << 1, s == m); propo((ind << 1) + 1, m + 1 == e);
    st[ind] = join(st[ind << 1], st[(ind << 1) + 1]);
}

void updateset(int ind, int s, int e, int p, ll v){
    propo(ind, s == e);
    if (s == e){
        st[ind] = {v, -1, 1, v};
        return;
    }
    int m = (s + e) >> 1;
    if (p <= m) updateset(ind << 1, s, m, p, v);
    else updateset((ind << 1) + 1, m + 1, e, p, v);
    propo(ind << 1, s == m); propo((ind << 1) + 1, m + 1 == e);
    st[ind] = join(st[ind << 1], st[(ind << 1) + 1]);
}

vals query(int ind, int s, int e, int l, int r){
    propo(ind, s == e);
    int m = (s + e) >> 1;
    if (l == s && r == e) return st[ind];
    else if (r <= m) return query(ind << 1, s, m, l, r);
    else if (l > m) return query((ind << 1) + 1, m + 1, e, l, r);
    else return join(query(ind << 1, s, m, l, m), query((ind << 1) + 1, m + 1, e, m + 1, r));
}

int findkth(int ind, int s, int e, int l, int r, int &k, ll v){
    propo(ind, s == e);
    if (st[ind].mx1 < v) return -1;
    if (l == s && r == e){
        if (st[ind].cnt1 < k){
            k -= st[ind].cnt1;
            return -1;
        }
    }
    if (s == e) return s;
    int m = (s + e) >> 1;
    if (r <= m) return findkth(ind << 1, s, m, l, r, k, v);
    else if (l > m) return findkth((ind << 1) + 1, m + 1, e, l, r, k, v);
    else{
        int lres = findkth(ind << 1, s, m, l, m, k, v);
        if (lres != -1) return lres;
        return findkth((ind << 1) + 1, m + 1, e, m + 1, r, k, v);
    }
}

void initialise(int N, int Q, int h[]) {
    nums = N;
	for (int i = 1; i <= N; i++) height[i] = h[i];
	init(1, 1, nums);
}

void cut(int l, int r, int k) {
	while (k > 0){
        vals v = query(1, 1, nums, l, r);
        if (v.mx1 == 0) break;
        v.mx2 = max(v.mx2, 0ll);
        if (k >= v.cnt1 * (v.mx1 - v.mx2)){
            updatemin(1, 1, nums, l, r, v.mx2);
            k -= v.cnt1 * (v.mx1 - v.mx2);
        }
        else{
            int quot = k / v.cnt1, rem = k % v.cnt1;
            if (rem == 0) updatemin(1, 1, nums, l, r, v.mx1 - quot);
            else{
                int remind = findkth(1, 1, nums, l, r, rem, v.mx1);
                updatemin(1, 1, nums, l, remind, v.mx1 - quot - 1);
                updatemin(1, 1, nums, remind + 1, r, v.mx1 - quot);
            }
            k = 0;
        }
	}
}

void magic(int i, int x) {
	updateset(1, 1, nums, i, x);
}

ll inspect(int l, int r) {
	return query(1, 1, nums, 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 412 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 412 KB Output is correct
3 Correct 67 ms 11932 KB Output is correct
4 Correct 82 ms 11864 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 5 ms 476 KB Output is correct
3 Runtime error 30 ms 26932 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 26876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

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 412 KB Output is correct
3 Correct 67 ms 11932 KB Output is correct
4 Correct 82 ms 11864 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 5 ms 476 KB Output is correct
7 Correct 76 ms 11860 KB Output is correct
8 Correct 94 ms 11900 KB Output is correct
9 Correct 61 ms 11844 KB Output is correct
10 Correct 114 ms 11952 KB Output is correct
11 Correct 71 ms 11908 KB Output is correct
12 Correct 12 ms 11604 KB Output is correct
13 Correct 54 ms 11604 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 412 KB Output is correct
3 Correct 67 ms 11932 KB Output is correct
4 Correct 82 ms 11864 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 5 ms 476 KB Output is correct
7 Runtime error 30 ms 26932 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -