oj.uz

Submission #516699

# Submission time Handle Problem Language Result Execution time Memory
516699 2022-01-21T23:28:27 Z couplefire Weirdtree (RMI21_weirdtree) C++17
23 / 100
 216 ms 34672 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, cnt-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){
    bool f = k==999;
    --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<=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;
}

Compilation message

weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:120:10: warning: unused variable 'f' [-Wunused-variable]
  120 |     bool f = k==999;
      |          ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26948 KB Output is correct
2 Correct 17 ms 27012 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26948 KB Output is correct
2 Correct 17 ms 27012 KB Output is correct
3 Correct 74 ms 28236 KB Output is correct
4 Correct 90 ms 28308 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 26976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 26976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 34564 KB Output is correct
2 Correct 216 ms 34672 KB Output is correct
3 Correct 48 ms 28612 KB Output is correct
4 Correct 67 ms 28492 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26948 KB Output is correct
2 Correct 17 ms 27012 KB Output is correct
3 Correct 74 ms 28236 KB Output is correct
4 Correct 90 ms 28308 KB Output is correct
5 Incorrect 22 ms 26976 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26948 KB Output is correct
2 Correct 17 ms 27012 KB Output is correct
3 Correct 74 ms 28236 KB Output is correct
4 Correct 90 ms 28308 KB Output is correct
5 Incorrect 22 ms 26976 KB Output isn't correct
6 Halted 0 ms 0 KB -