oj.uz

Submission #516700

# Submission time Handle Problem Language Result Execution time Memory
516700 2022-01-21T23:37:36 Z couplefire Weirdtree (RMI21_weirdtree) C++17
100 / 100
 586 ms 35644 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1<<19;

struct node{
    ll sum; int mx, cmx, smx;

    node(int x = 0){
        sum = mx = x;
        smx = 0;
        cmx = 1;
    }
    
    node(node a, node b){
        if(a.mx<b.mx || (a.mx==b.mx && a.smx<b.smx))
            swap(a, b);
        sum = a.sum+b.sum;
        if(a.mx>b.mx){
            mx = a.mx;
            cmx = a.cmx;
            smx = max(a.smx, b.mx);
        } else{
            mx = a.mx;
            cmx = a.cmx+b.cmx;
            smx = a.smx;
        }
    }
} tree[N<<1];

void push(int v, int tl, int tr){
    if(tl==tr) return;
    if(tree[v<<1].mx>tree[v].mx)
        tree[v<<1].sum -= tree[v<<1].cmx*(tree[v<<1].mx-tree[v].mx),
        tree[v<<1].mx = tree[v].mx;
    if(tree[v<<1|1].mx>tree[v].mx)
        tree[v<<1|1].sum -= tree[v<<1|1].cmx*(tree[v<<1|1].mx-tree[v].mx),
        tree[v<<1|1].mx = tree[v].mx;
}

void build(vector<int>& h, int v = 1, int tl = 0, int tr = N-1){
    if(tl==tr){
        tree[v] = node(h[tl]);
        return;
    }
    int tm = (tl+tr)>>1;
    build(h, v<<1, tl, tm);
    build(h, v<<1|1, tm+1, tr);
    tree[v] = node(tree[v<<1], tree[v<<1|1]);
}

void upd(int l, int r, int x, int v = 1, int tl = 0, int tr = N-1){
    if(tr<l || tl>r || x>=tree[v].mx) return;
    push(v, tl, tr);
    if(l<=tl && tr<=r && (x>tree[v].smx || x==0)){
        tree[v].sum -= 1ll*tree[v].cmx*(tree[v].mx-x);
        tree[v].mx = x; 
        return;
    }
    int tm = (tl+tr)>>1;
    upd(l, r, x, v<<1, tl, tm);
    upd(l, r, x, v<<1|1, tm+1, tr);
    tree[v] = node(tree[v<<1], tree[v<<1|1]);
}

void apply(int pos, int x, int v = 1, int tl = 0, int tr = N-1){
    if(tr<pos || tl>pos) return;
    push(v, tl, tr);
    if(tl==tr){
        tree[v] = node(x);
        return;
    }
    int tm = (tl+tr)>>1;
    apply(pos, x, v<<1, tl, tm);
    apply(pos, x, v<<1|1, tm+1, tr);
    tree[v] = node(tree[v<<1], tree[v<<1|1]);
}

node query(int l, int r, int v = 1, int tl = 0, int tr = N-1){
    if(tr<l || tl>r) return node();
    push(v, tl, tr);
    if(l<=tl && tr<=r) return tree[v];
    int tm = (tl+tr)>>1;
    return node(query(l, r, v<<1, tl, tm), query(l, r, v<<1|1, tm+1, tr));
}

pair<int, int> find(int l, int r, int x, int cnt, int v = 1, int tl = 0, int tr = N-1){
    if(tr<l || tl>r) return {cnt, -1};
    push(v, tl, tr);
    if(l<=tl && tr<=r){
        if(tree[v].mx!=x) return {cnt, -1};
        if(tree[v].cmx<cnt) return {cnt-tree[v].cmx, -1};
        while(tl<tr){
            push(v, tl, tr);
            int tm = (tl+tr)>>1;
            if(tree[v<<1].mx==x && tree[v<<1].cmx>=cnt)
                v = v<<1, tr = tm;
            else{
                cnt -= (tree[v<<1].mx==x?tree[v<<1].cmx:0);
                v = v<<1|1; tl = tm+1;
            }
        }
        return {0, tl};
    }
    int tm = (tl+tr)>>1;
    pair<int, int> lres = find(l, r, x, cnt, v<<1, tl, tm);
    if(lres.second!=-1) return lres;
    return find(l, r, x, lres.first, v<<1|1, tm+1, tr);
}

void initialise(int n, int q, int h[]){
    vector<int> arr(N, 0);
    for(int i = 0; i<n; ++i)
        arr[i] = h[i+1];
    build(arr);
}

void cut(int l, int r, int k){
    --l; --r;
    while(k){
        node tmp = query(l, r);
        if(tmp.mx==0) break;
        ll ops = 1ll*tmp.cmx*(tmp.mx-tmp.smx);
        if(ops<=(ll)k){
            k -= ops;
            upd(l, r, tmp.smx);
        } else{
            if(k%tmp.cmx==0){
                upd(l, r, tmp.mx-k/tmp.cmx);
                k = 0; continue;
            }
            int pos = find(l, r, tmp.mx, k%tmp.cmx).second;
            upd(l, pos, tmp.mx-k/tmp.cmx-1);
            upd(pos+1, r, tmp.mx-k/tmp.cmx);
            k = 0;
        }
    }
}

void magic(int i, int x){
    --i;
    apply(i, x);
}

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26956 KB Output is correct
2 Correct 18 ms 26936 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26956 KB Output is correct
2 Correct 18 ms 26936 KB Output is correct
3 Correct 80 ms 27340 KB Output is correct
4 Correct 90 ms 27340 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26956 KB Output is correct
2 Correct 22 ms 26992 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26956 KB Output is correct
2 Correct 22 ms 26992 KB Output is correct
3 Correct 586 ms 35644 KB Output is correct
4 Correct 397 ms 35524 KB Output is correct
5 Correct 464 ms 35572 KB Output is correct
6 Correct 356 ms 35644 KB Output is correct
7 Correct 47 ms 27340 KB Output is correct
8 Correct 62 ms 27352 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 27340 KB Output is correct
2 Correct 62 ms 27352 KB Output is correct
3 Correct 239 ms 28132 KB Output is correct
4 Correct 199 ms 28108 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26956 KB Output is correct
2 Correct 18 ms 26936 KB Output is correct
3 Correct 80 ms 27340 KB Output is correct
4 Correct 90 ms 27340 KB Output is correct
5 Correct 21 ms 26956 KB Output is correct
6 Correct 22 ms 26992 KB Output is correct
7 Correct 47 ms 27340 KB Output is correct
8 Correct 62 ms 27352 KB Output is correct
9 Correct 83 ms 28280 KB Output is correct
10 Correct 91 ms 28356 KB Output is correct
11 Correct 73 ms 28360 KB Output is correct
12 Correct 98 ms 28364 KB Output is correct
13 Correct 109 ms 28256 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26956 KB Output is correct
2 Correct 18 ms 26936 KB Output is correct
3 Correct 80 ms 27340 KB Output is correct
4 Correct 90 ms 27340 KB Output is correct
5 Correct 21 ms 26956 KB Output is correct
6 Correct 22 ms 26992 KB Output is correct
7 Correct 586 ms 35644 KB Output is correct
8 Correct 397 ms 35524 KB Output is correct
9 Correct 464 ms 35572 KB Output is correct
10 Correct 356 ms 35644 KB Output is correct
11 Correct 239 ms 28132 KB Output is correct
12 Correct 199 ms 28108 KB Output is correct
13 Correct 83 ms 28280 KB Output is correct
14 Correct 91 ms 28356 KB Output is correct
15 Correct 73 ms 28360 KB Output is correct
16 Correct 98 ms 28364 KB Output is correct
17 Correct 109 ms 28256 KB Output is correct
18 Correct 47 ms 27340 KB Output is correct
19 Correct 62 ms 27352 KB Output is correct
20 Correct 340 ms 35044 KB Output is correct
21 Correct 429 ms 35508 KB Output is correct
22 Correct 307 ms 35404 KB Output is correct
23 Correct 439 ms 35488 KB Output is correct
24 Correct 336 ms 35244 KB Output is correct