oj.uz

Submission #498661

# Submission time Handle Problem Language Result Execution time Memory
498661 2021-12-26T04:45:35 Z model_code Weirdtree (RMI21_weirdtree) C++17
100 / 100
 881 ms 29632 KB 
// weirdtree_100_segtreebeats_ruxandra.cpp

#include <bits/stdc++.h>
#include "weirdtree.h"
#define DIMN 300010
using namespace std;

struct segm_tree{
    long long sum;
    int maxi1, cntmaxi1, maxi2, lazy;
    /// lazy este cea mai mare valoare care poate sa apara ever in subarb
} aint[4*DIMN];

int v[DIMN], n;

segm_tree combine (segm_tree a , segm_tree b){
    segm_tree c;

    c.sum = a.sum + b.sum;

    if (a.maxi1 > b.maxi1){
        c.maxi1 = a.maxi1;
        c.cntmaxi1 = a.cntmaxi1;

        c.maxi2 = max(a.maxi2 , b.maxi1);
    }
    else if (a.maxi1 < b.maxi1){
        c.maxi1 = b.maxi1;
        c.cntmaxi1 = b.cntmaxi1;

        c.maxi2 = max(b.maxi2 , a.maxi1);
    }
    else { /// egale
        c.maxi1 = a.maxi1;
        c.cntmaxi1 = a.cntmaxi1 + b.cntmaxi1;

        c.maxi2 = max(b.maxi2 , a.maxi2);
    }

    c.lazy = max(a.lazy, b.lazy);

    return c;
}

void lazy_update (int nod , int st , int dr){
    /// the maximum value in the interval st , dr must be aint[nod].lazy
    if (st == dr)
        return;

    if (aint[nod].lazy < aint[2 * nod].maxi1){
        aint[2 * nod].sum = aint[2 * nod].sum - 1LL * aint[2 * nod].maxi1 * aint[2 * nod].cntmaxi1 +
                                                 1LL * aint[nod].lazy * aint[2 * nod].cntmaxi1;
        aint[2 * nod].maxi1 = aint[nod].lazy;
        aint[2 * nod].lazy = min(aint[2 * nod].lazy , aint[nod].lazy);
    }

    if (aint[nod].lazy < aint[2 * nod + 1].maxi1){
        aint[2 * nod + 1].sum = aint[2 * nod + 1].sum - 1LL * aint[2 * nod + 1].maxi1 * aint[2 * nod + 1].cntmaxi1 +
                                                 1LL * aint[nod].lazy * aint[2 * nod + 1].cntmaxi1;
        aint[2 * nod + 1].maxi1 = aint[nod].lazy;
        aint[2 * nod + 1].lazy = min(aint[2 * nod + 1].lazy , aint[nod].lazy);
    }

}

void build (int nod, int st , int dr){
    int mid = (st + dr)/2;

    if (st == dr){
        aint[nod].sum = v[st];
        aint[nod].maxi1 = v[st];
        aint[nod].cntmaxi1 = 1;
        aint[nod].maxi2 = 0;
        aint[nod].lazy = v[st];
        return;
    }

    build (2 * nod , st , mid);
    build (2 * nod + 1 , mid + 1 , dr);

    aint[nod] = combine(aint[2 * nod] , aint[2 * nod + 1]);

}

segm_tree query (int nod , int st , int dr, int l , int r){
    segm_tree sol = {0, 0 , 0 , 0, 0};
    int mid = (st + dr)/2;
    lazy_update (nod , st , dr);
    if (l <= st && dr <= r){
        sol = aint[nod];
        return sol;
    }

    if (l <= mid){
        sol = combine(sol , query(2 * nod , st , mid , l , r));
    }
    if (mid + 1 <= r){
        sol = combine(sol , query(2 * nod + 1 , mid + 1 , dr , l , r));
    }

    lazy_update (2 * nod , st , mid);
    lazy_update (2 * nod + 1 , mid + 1 , dr);
    aint[nod] = combine(aint[2 * nod] , aint[2 * nod + 1]);

    return sol;

}

void update (int nod , int st , int dr , int l , int r , int &capacity, int maxi){
    int mid = (st + dr)/2;

    lazy_update (nod , st , dr);

    if (st > r || dr < l || aint[nod].maxi1 <= maxi - (capacity > 0)){
        return; /// nothing to change here
    }

    if (l <= st && dr <= r && aint[nod].maxi1 > maxi - (capacity > 0) &&
         (aint[nod].maxi2 < maxi - (capacity > 0) || (aint[nod].cntmaxi1 == dr - st + 1)) &&
        (!capacity || capacity >= aint[nod].cntmaxi1)){
        if (!capacity){
            aint[nod].sum = aint[nod].sum - 1LL * aint[nod].maxi1 * aint[nod].cntmaxi1
                                          + 1LL * maxi * aint[nod].cntmaxi1;
            aint[nod].lazy = maxi;
            aint[nod].maxi1 = maxi;
        } else { /// the whole interval is 1 less
            aint[nod].sum = aint[nod].sum - 1LL * aint[nod].maxi1 * aint[nod].cntmaxi1
                                          + 1LL * (maxi - 1) * aint[nod].cntmaxi1;
            aint[nod].lazy = maxi - 1;
            aint[nod].maxi1 = maxi - 1;
            capacity -= aint[nod].cntmaxi1;
        }

        lazy_update (nod,st,dr);
        return;
    }

    if (l <= mid)
        update (2 * nod , st , mid , l , r , capacity , maxi);

    if (mid + 1 <= r)
        update (2 * nod + 1 , mid + 1 , dr , l , r , capacity , maxi);

    lazy_update (2 * nod , st , mid);
    lazy_update (2 * nod + 1 , mid + 1 , dr);

    aint[nod] = combine(aint[2 * nod] , aint[2 * nod + 1]);

}

void update_value (int nod , int st , int dr , int pos , int val){
    int mid = (st + dr)/2;

    lazy_update (nod , st , dr);

    if (st == dr){
        aint[nod].sum = val;
        aint[nod].maxi1 = val;
        aint[nod].cntmaxi1 = 1;
        aint[nod].maxi2 = 0;
        aint[nod].lazy = val;
        return;
    }

    if (pos <= mid)
        update_value (2 * nod , st , mid , pos , val);
    else
        update_value (2 * nod + 1 , mid + 1 , dr , pos , val);

    lazy_update (2 * nod , st , mid);
    lazy_update (2 * nod + 1 , mid + 1 , dr);

    aint[nod] = combine(aint[2 * nod] , aint[2 * nod + 1]);

}

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

void cut (int l, int r, int k){
    segm_tree ans;
    long long cuts;
    int capacity;
    while (k){
        ans = query (1 , 1 , n , l , r);

        if (ans.maxi1 == 0){
            /// not much you can do
            return;
        }

        cuts = 1LL * (ans.maxi1 - ans.maxi2) * ans.cntmaxi1;

        if (cuts <= k){
            /// all values equal to maxi1 become equal to maxi2 in [l , r]
            k -= cuts;
            capacity = 0;
            update (1 , 1 , n , l , r , capacity, ans.maxi2);
        }
        else {
            /// too many values bigger than maxi2, do stuff
            int valueToReach = ans.maxi1 - k / ans.cntmaxi1;
            capacity = k % ans.cntmaxi1;
            update (1 , 1 , n , l , r , capacity , valueToReach);
            k = 0;
        }

    }
}

void magic (int i, int k){
    update_value (1 , 1 , n , i , k);
}

long long 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 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 120 ms 7572 KB Output is correct
4 Correct 115 ms 7504 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 763 ms 29632 KB Output is correct
4 Correct 796 ms 29596 KB Output is correct
5 Correct 881 ms 29584 KB Output is correct
6 Correct 752 ms 29416 KB Output is correct
7 Correct 9 ms 7116 KB Output is correct
8 Correct 75 ms 7152 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7116 KB Output is correct
2 Correct 75 ms 7152 KB Output is correct
3 Correct 203 ms 28856 KB Output is correct
4 Correct 153 ms 28960 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 120 ms 7572 KB Output is correct
4 Correct 115 ms 7504 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 9 ms 7116 KB Output is correct
8 Correct 75 ms 7152 KB Output is correct
9 Correct 117 ms 7572 KB Output is correct
10 Correct 130 ms 7492 KB Output is correct
11 Correct 123 ms 7496 KB Output is correct
12 Correct 148 ms 7532 KB Output is correct
13 Correct 167 ms 7540 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 120 ms 7572 KB Output is correct
4 Correct 115 ms 7504 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 763 ms 29632 KB Output is correct
8 Correct 796 ms 29596 KB Output is correct
9 Correct 881 ms 29584 KB Output is correct
10 Correct 752 ms 29416 KB Output is correct
11 Correct 203 ms 28856 KB Output is correct
12 Correct 153 ms 28960 KB Output is correct
13 Correct 117 ms 7572 KB Output is correct
14 Correct 130 ms 7492 KB Output is correct
15 Correct 123 ms 7496 KB Output is correct
16 Correct 148 ms 7532 KB Output is correct
17 Correct 167 ms 7540 KB Output is correct
18 Correct 9 ms 7116 KB Output is correct
19 Correct 75 ms 7152 KB Output is correct
20 Correct 614 ms 28628 KB Output is correct
21 Correct 665 ms 28868 KB Output is correct
22 Correct 644 ms 28788 KB Output is correct
23 Correct 695 ms 28768 KB Output is correct
24 Correct 607 ms 28704 KB Output is correct